分数: 800 点
问题陈述
有 N 方格排成一排,编号 1 to N 从左到右。高桥将在这些还没有积木的广场上堆放积木。
他想把方块均匀地堆放在方格上,所以他会重复下面的操作,直到有 H 每个方格上都有方块:
- 让 M 和 m 分别是当前在正方形上堆叠的块的最大和最小数量。选择一个正方形,其上 将 m 块堆叠起来(如果有多个这样的方格,则选择其中任何一个),并在该方格上添加正数个块,以便至少有 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
(Square 上的块数)的可能转换 1,Square 上的块数 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
2 30 15
示例输出 2
94182806
示例输入 3
31415 9265 3589
示例输出 3
312069529
请务必打印模数 给你一棵带有 10^9+7.