Паркет для олігарха
У одного олігарха є загородній будинок. Гостьова зала у цьому домі має форму прямокутника розміром 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.
Вихідні дані
Ціле число, рівне шуканій кількості способів.