Parquet for an Oligarch
An oligarch owns a country house with a guest room shaped like a rectangle, measuring NxM meters. One day, while visiting the house for some relaxation, the oligarch decided that the guest room's floor needed a new parquet. The designer proposed using parquet planks measuring 10x20 cm, which infuriated the oligarch.
"In my guest room, such tiny planks? Are you all out of your minds? The planks should be sized 1xK meters, and K should be as large as possible, ensuring that 2·K > N."
- "And what should the parquet pattern be?" the designer asked calmly, used to the oligarch's whims.
- "Are there many options?"
- "Very many."
- "Tell me how many, and I'll choose the one I need."
"I should have kept quiet!" thought the designer, as he began to calculate the options. Now, it's your turn to count them.
Write a program that takes as input the integers N, M, and K, and returns the number of ways to cover a rectangular room measuring NxM meters with rectangular planks measuring 1xK meters. The planks must be aligned so that their sides are parallel to the sides of the room.
Input
The input consists of three lines, each containing an integer: N - the width of the room (in meters), M - the length of the room (in meters), and K - the length of the plank (in meters). All numbers are natural and do not exceed 1000. The number N is strictly less than 2·K. The numbers N, M, and K are such that the total number of ways does not exceed 2^63-1.
Output
Output a single integer representing the number of ways to cover the room.