Score : 800 points
There are N squares arranged in a row, numbered 1 to N from left to right. Takahashi will stack building blocks on these squares, on which there are no blocks yet.
He wants to stack blocks on the squares evenly, so he will repeat the following operation until there are H blocks on every square:
Tell him how many ways there are to have H blocks on every square by repeating this operation. Since there can be extremely many ways, print the number modulo 10^9+7.
Input is given from Standard Input in the following format:
N H D
Print the number of ways to have H blocks on every square, modulo 10^9+7.
2 2 1
6
The possible transitions of (the number of blocks on Square 1, the number of blocks on Square 2) are as follows:
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2)
(0, 0) -> (0, 1) -> (2, 1) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 2) -> (2, 2)
Thus, there are six ways to have two blocks on every square.
2 30 15
94182806
31415 9265 3589
312069529
Be sure to print the number modulo 10^9+7.