Паркет для олигарха
У одного олигарха есть загородный дом. Гостевой зал в этом доме имеет форму прямоугольника размером NxM метров. Как-то раз олигарх приехал в загородный дом отдохнуть и решил, что пол в гостевом зале необходимо покрыть паркетом. Дизайнер предложил выложить паркет из дощечек размером 10x20 см и в ответ услышал справедливое возмущение олигарха.
- Чтобы в моем гостевом зале, да такие мизерные дощечки - вы что, с ума там все посходили? Дощечки должны быть размером 1xK метров, причем K нужно выбрать побольше - так, чтобы выполнялось неравенство 2·K > N.
- А каким должен быть узор паркета? - спокойно поинтересовался дизайнер, привыкший к причудам олигарха.
- А что, существует много вариантов?
- Очень много.
- Скажите мне сколько и я выберу из них тот, который мне нужен.
"Лучше бы я молчал!" - подумал дизайнер и ушел считать варианты. Посчитайте их и вы.
Напишите программу, получающую на вход целые числа N, M и K и возвращающий количество способов покрытия прямоугольного зала размером NxM метров прямоугольными дощечками размера 1xK метров. Дощечки должны быть расположены так, чтобы их стороны были параллельны сторонам зала.
Входные данные
В трёх строках 3 целых числа: N - ширина зала (в метрах), M - длина зала (в метрах), K - длина дощечки (в метрах). Все числа натуральные и не превышают 1000. Число N строго меньше, чем 2·K. Числа N, M и K таковы, что искомое количество способов не превосходит 2^63-1.
Выходные данные
Целое число, равное искомому количеству способов.