The Master Builder's Challenge#1439
"The Master Builder's Challenge" is the most popular construction game show on television! In today's episode, contestants face a unique puzzle: they must cover a rectangular floor measuring N \times M meters. Initially, the producers suggested using standard 10 \times 20 cm tiles, but the charismatic host had another idea.
"Standard tiles? That would be too easy for our master builders! Let's make it interesting — contestants can only use large planks sized 1 \times K meters, where must be large enough that 2 \cdot K > N!"
"And what pattern should the contestants aim for?" asked the game designer, already anticipating the host's next move.
"Are there many possible patterns?"
"Very many."
"Perfect! Tell me exactly how many patterns are possible, and we'll display that number to build suspense before revealing the contestants' solutions!"
"Why did I ask?" thought the game designer, reaching for the calculator. Now it's your turn to help count them!
Write a program that takes as input the integers , , and , and returns the number of ways to cover a rectangular floor measuring N \times M meters with planks measuring 1 \times K meters. The planks must be placed so that their sides are parallel to the sides of the floor.
The input consists of three lines. Each line contains a single integer: — the width of the floor (in meters), — the length of the floor (in meters), and — the length of each plank (in meters). All numbers are positive and do not exceed . The number is strictly less than 2 \cdot K. The numbers , , and are such that the total number of ways does not exceed 2^{63}-1.
Output a single integer representing the number of ways to cover the floor.
Example 1