Виклик Майстра-Будівельника#1439
"Виклик Майстра-Будівельника" — найпопулярніше телевізійне шоу з будівництва! У сьогоднішньому епізоді учасники стикаються з унікальною головоломкою: їм потрібно вкрити прямокутну підлогу розміром N \times M метрів. Спочатку продюсери запропонували використати стандартну плитку 10 \times 20 см, але харизматичний ведучий вирішив інакше.
"Стандартні плитки? Для наших майстрів це надто просто! Треба зробити цікавіше — учасники можуть використовувати лише великі дошки розміром 1 \times K метрів, причому має бути таким великим, щоб 2 \cdot K > N!"
"А який візерунок мають скласти учасники?" — спитав розробник ігор, вже передчуваючи наступний хід ведучого.
"Невже існує багато варіантів розташування?"
"Дуже багато."
"Ідеально! Скажіть мені точно, скільки варіантів існує, ми виведемо цю цифру на екран, щоб нагнати інтригу перед розв'язаннями учасників!"
"Чому я спитав?" — подумав розробник ігор, беручись за калькулятор. Тепер ваша черга допомогти з підрахунком!
Напишіть програму, яка отримує на вхід числа , та , і повертає кількість способів укласти дошки розміром 1 \times K метрів, щоб повністю покрити прямокутну підлогу розміром N \times M метрів. Дошки потрібно розташовувати так, щоб їхні сторони були паралельними сторонам підлоги.
Вхід складається з трьох рядків. У кожному рядку міститься одне ціле число: — ширина підлоги (у метрах), — довжина підлоги (у метрах), — довжина кожної дошки (у метрах). Усі числа додатні та не перевищують . Число строго менше за 2 \cdot K. Числа , і такі, що загальна кількість варіантів не перевищує 2^{63}-1.
Виведіть одне ціле число — кількість способів вкрити підлогу.
Приклад 1