У одного олигарха есть загородный дом. Гостевой зал в этом доме имеет форму прямоугольника размером NxM метров. Как-то раз олигарх приехал в загородный дом отдохнуть и решил, что пол в гостевом зале необходимо покрыть паркетом. Дизайнер предложил выложить паркет из дощечек размером 10x20 см и в ответ услышал справедливое возмущение олигарха.

   - Чтобы в моем гостевом зале, да такие мизерные дощечки - вы что, с ума там все посходили? Дощечки должны быть размером 1xK метров, причем K нужно выбрать побольше - так, чтобы выполнялось неравенство 2·K > N.

   - А каким должен быть узор паркета? - спокойно поинтересовался дизайнер, привыкший к причудам олигарха.

   - А что, существует много вариантов?

   - Очень много.

   - Скажите мне сколько и я выберу из них тот, который мне нужен.

   "Лучше бы я молчал!" - подумал дизайнер и ушел считать варианты. Посчитайте их и вы.

   Напишите программу, получающую на вход целые числа N, M и K и возвращающий количество способов покрытия прямоугольного зала размером NxM метров прямоугольными дощечками размера 1xK метров. Дощечки должны быть расположены так, чтобы их стороны были параллельны сторонам зала.

   Входные данные

   В трёх строках 3 целых числа: N - ширина зала (в метрах), M - длина зала (в метрах), K - длина дощечки (в метрах). Все числа натуральные и не превышают 1000. Число N строго меньше, чем 2·K. Числа N, M и K таковы, что искомое количество способов не превосходит 2⁶³-1.

   Выходные данные

   Целое число, равное искомому количеству способов.