← 返回题目列表

AtCoder · diverta2019_2_e

E. 平衡桩

中文机器翻译题面 查看原题

分数: 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.