题目描述

国籍不明，年龄不详的赌徒 Picar 和 Roman 正在玩一个游戏。

正如一些经典的和赌博相关的问题中提到的那样，这个游戏是纯随机的。

每一轮游戏中，参加游戏的赌徒需要先选定一个要下注的号码，并将要下注的金额支付给系统（不妨记游戏中使用的货币单位为 G）。选择的号码可以是 $1$ 至 $n$ 之间的任意整数（$n$ 是固定的正整数），其中号码 $i$ 对应正整数权重 $a_i$。记 $s=\sum_{i=1}^n a_i$，那么系统在每轮游戏中选出号码 $i$ 的概率总为 $a_i/s$。所有参加游戏的赌徒下注结束之后，系统将会按照给定的概率随机挑选一个号码作为中奖号码。下注了中奖号码的赌徒可以根据其下注的金额及中奖号码对应的概率获得相应的奖金，而下注了其它号码的赌徒不会获得任何奖金。

至于返还奖金的比例，一个自然的想法是：无论一个赌徒给哪个号码下注，其期望获得的奖金应该与其下注的金额相等。也就是说，如果一个赌徒为号码 $i$ 支付了 $x$ G，那么他中奖时应获得 $sx/a_i$ 的奖金。

这个游戏的一个小缺陷是，货币 G 的最小面额是 $1$ G，也就是说系统不能返还奖金的小数部分。为了避免这一现象，规定每次下注的金额必须是 $k$ 的正整数倍（其中 $k$ 是固定的正整数）。游戏的设计者需要保证，在给定 $k$ 之后，$k s$ 是每个 $a_i$（$i = 1, \ldots , n$）的正整数倍，这样计算奖金时就不会出现非整数值。

Picar 和 Roman 觉得这游戏很有意思，他们希望在不同的参数下各玩几轮。但是他们不喜欢太大的数字，所以 $s$ 不能超过一个给定的正整数 $m$（显然，由于权重之和最多为 $m$，每个权重也最多是 $m$）。对于权重集合相同的方案，仅仅打乱权重的顺序对游戏体验的改变不大，所以 Picar 和 Roman 认为，两组权重参数本质不同当且仅当这两组参数对应的可重集合不同。换句话说，如果将两组权重参数 $a_1, \ldots, a_n$ 和 $b_1, \ldots, b_n$ 分别从小到大排序，得到 $1\le\alpha_1\le\alpha_2\le\cdots\le\alpha_n$ 和 $1\le\beta_1\le\beta_2\le\cdots\le\beta_n$，那么这两组参数本质不同当且仅当存在下标 $i\in\left\{1, \ldots, n\right\}$ 使得 $\alpha_i \ne \beta_i$。

Picar 和 Roman 想知道，给定 $n, m, k$，有多少种满足“要求”的本质不同的参数方案。需要注意的是，由于这里吝啬的 Picar 和 Roman 只给了你 $k$，你需要保证你统计的每个方案中，$ks$ 是每个权重 $a_i$（$i = 1, \ldots , n$）的正整数倍。

输入格式

输入仅一行，包括三个正整数 $n, m, k$，两个数之间由一个空格隔开。

输出格式

输出一个非负整数，表示方案数对 ${10}^9+7$ 取模的结果。

3 9 1

6

3 9 10

13

10 2000 20201003

365520548

提示

【样例解释 #1】

满足要求的方案有：

1. $3=1+1+1$；
2. $4=1+1+2$；
3. $6=1+2+3$；
4. $6=2+2+2$；
5. $8=2+2+4$；
6. $9=3+3+3$。

请特别注意，本题的方案是顺序无关的。

【样例解释 #2】

除了样例 #1 中的方案外，还有：

7. $5=1+2+2$；
8. $6=1+1+4$；
9. $7=1+1+5$；
10. $8=1+2+5$；
11. $9=1+2+6$；
12. $9=1+3+5$；
13. $9=2+2+5$。

【数据范围】

对于 $100\%$ 的数据，保证 $1\le n\le 10$，$1\le m \le 2000$，$1\le k \le 10^9$。

【提示】

赌博有风险，建议远离赌博。

请选手在提交评测之前确认自己对于数据范围的理解正确。如果你的理解不是正确的，你将有可能获得 Wrong Answer 的评测结果。

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 https://github.com/yylidiw/thupc_1/tree/master 查看。