/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 個のマスが横一列に並んでおり、左から順に 1 から N までの番号がつけられています。高橋君はこれらのマスに積み木を積もうとしています。 まだそれぞれのマスには積み木が 1 つも積まれていません。
積み木をバランス良く積みたい高橋君は、以下の操作を繰り返して全てのマスに積み木がちょうど H 個ずつ積まれている状態にしようとしています。
- 1 マスに積まれている積み木の最大値を M 個、最小値を m 個とする。m 個の積み木が置かれているマスを 1 つ選び (複数ある場合はどれを選んでもよい)、そのマスに積まれた積み木が M 個以上 M + D 個以下になるように積み木を正の個数積む。
高橋君のために、この操作を繰り返して全てのマスに積み木がちょうど H 個積まれている状態にする方法が何通りあるか数えてあげてください。答えは非常に大きくなる場合があるので、10^9+7 で割った余りを出力してください。
制約
- 2 \leq N \leq 10^6
- 1 \leq D \leq H \leq 10^6
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N H D
出力
全てのマスに積み木がちょうど H 個積まれている状態にする方法の個数を 10^9+7 で割った余りを出力せよ。
入力例 1
2 2 1
出力例 1
6
(マス 1 に積まれた積み木の個数, マス 2 に積まれた積み木の個数) は次のように変化させることができます。
-
(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)
よって、全てのマスに積み木がちょうど 2 個積まれている状態にする方法の個数は 6 通りです。
入力例 2
2 30 15
出力例 2
94182806
入力例 3
31415 9265 3589
出力例 3
312069529
個数を 10^9+7 で割った余りを出力することに注意してください。
Score : 800 points
Problem Statement
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:
- Let M and m be the maximum and minimum numbers of blocks currently stacked on a square, respectively. Choose a square on which m blocks are stacked (if there are multiple such squares, choose any one of them), and add a positive number of blocks on that square so that there will be at least M and at most M + D blocks on that 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.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq D \leq H \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N H D
Output
Print the number of ways to have H blocks on every square, modulo 10^9+7.
Sample Input 1
2 2 1
Sample Output 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.
Sample Input 2
2 30 15
Sample Output 2
94182806
Sample Input 3
31415 9265 3589
Sample Output 3
312069529
Be sure to print the number modulo 10^9+7.