Problem Description

There are $ N $ squares arranged in a row, numbered from $ 1 $ to $ N $ in order from left to right. Takahashi is trying to stack wooden blocks on these squares. Currently, no wooden blocks are stacked on any of the squares.

Takahashi wants to stack the wooden blocks in a balanced manner and is trying to achieve a state where exactly $ H $ wooden blocks are stacked on each square by repeating the following operation:

• Let $ M $ be the maximum number of wooden blocks stacked on a single square, and $ m $ be the minimum number of wooden blocks stacked on a single square. Choose one square that has $ m $ wooden blocks (if there are multiple, any of them can be chosen), and add a positive number of wooden blocks to this square so that the number of wooden blocks on it is between $ M $ and $ M + D $ (inclusive).

For Takahashi, please count how many ways there are to repeat this operation to achieve a state where exactly $ H $ wooden blocks are stacked on each square. Since the answer can be very large, output the answer modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ H $ $ D $

Output Format

Output the number of ways to achieve a state where exactly $ H $ wooden blocks are stacked on each square, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

2 2 1

Sample Output #1

6

Sample Input #2

2 30 15

Sample Output #2

94182806

Sample Input #3

31415 9265 3589

Sample Output #3

312069529

Notes/Hints

Constraints

• $2 \leq N \leq 10^6$
• $1 \leq D \leq H \leq 10^6$
• All inputs are integers.

Sample Explanation 1

The number of wooden blocks stacked on squares $ 1 $ and $ 2 $ can change 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 $ 6 $ ways to achieve a state where exactly $ 2 $ wooden blocks are stacked on each square.

Sample Explanation 3

Note that you should output the number modulo $ 10^9+7 $.

见题面 Input 部分

见题面 Output 部分