You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Balanced Piles

题目描述

有一个长度为 $N(2\le N \le 10^6)$ 的数组，一开始所有元素均为 $0$。

设 $M$ 为当前数组中的最大元素，$m$ 是当前数组中的最小元素，你可以执行若干次以下操作：

• 选择一个大小为 $m$ 的元素，把他变为 $x$，其中 $M\le x \le M+D$ 且 $m<x$。

求有多少种操作方法使得数组中的所有元素均为 $H$，对 $10^9+7$ 取模。

$1\le D\le H\le10^6$

输入格式

输入格式如下，一行三个正整数 $N,H,D$ 。

$N$ $H$ $D$

输出格式

答案模 $10^9+7$ 的值。

样例 #1

样例输入 #1

2 2 1

样例输出 #1

6

样例 #2

样例输入 #2

2 30 15

样例输出 #2

94182806

样例 #3

样例输入 #3

31415 9265 3589

样例输出 #3

312069529

提示

制約

• $2\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ D\ \leq\ H\ \leq\ 10^6$
• 输入都是整数

样例解释 1

$6$ 种操作方式如下：

• $(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)$