eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Паркет для олігарха

Паркет для олігарха

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

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

Вихідні дані

Ціле число, рівне шуканій кількості способів.

Приклад

Вхідні дані #1
3
2
2
Вихідні дані #1
3