Description

Two gamblers, Picar and Roman, of unknown nationality and age, are playing a game.

As mentioned in some classic gambling-related problems, this game is purely random.

In each round, every gambler who participates must first choose a number to bet on and pay the bet amount to the system (let the currency unit used in the game be G). The chosen number can be any integer from $1$ to $n$ (where $n$ is a fixed positive integer), and number $i$ corresponds to a positive integer weight $a_i$. Let $s=\sum_{i=1}^n a_i$. Then, in each round, the system always selects number $i$ with probability $a_i/s$. After all gamblers finish betting, the system randomly picks one number as the winning number according to the given probabilities. A gambler who bet on the winning number can receive a prize based on the bet amount and the probability of the winning number, while gamblers who bet on other numbers receive no prize.

As for the payout ratio, a natural idea is: no matter which number a gambler bets on, their expected prize should equal their bet amount. That is, if a gambler pays $x$ G for number $i$, then if they win, they should receive a prize of $sx/a_i$.

A small flaw of this game is that the minimum denomination of currency G is $1$ G, meaning the system cannot pay back fractional parts of prizes. To avoid this, the bet amount each time must be a positive integer multiple of $k$ (where $k$ is a fixed positive integer). The game designer must ensure that after $k$ is fixed, $k s$ is a positive integer multiple of every $a_i$ ($i = 1, \ldots , n$), so that no non-integer values appear when calculating prizes.

Picar and Roman find this game interesting and want to play several rounds under different parameters. But they do not like very large numbers, so $s$ cannot exceed a given positive integer $m$ (obviously, since the sum of weights is at most $m$, each weight is also at most $m$). For two schemes with the same set of weights, merely permuting the order of weights does not change the experience much, so Picar and Roman believe that two sets of weight parameters are essentially different if and only if the corresponding multisets are different. In other words, if we sort the two sets of weight parameters $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ in nondecreasing order to get $1\le\alpha_1\le\alpha_2\le\cdots\le\alpha_n$ and $1\le\beta_1\le\beta_2\le\cdots\le\beta_n$, then the two sets are essentially different if and only if there exists an index $i\in\left\{1, \ldots, n\right\}$ such that $\alpha_i \ne \beta_i$.

Picar and Roman want to know: given $n, m, k$, how many essentially different parameter schemes satisfy the “requirements”. Note that since the stingy Picar and Roman only give you $k$, you must ensure that in every scheme you count, $k s$ is a positive integer multiple of every weight $a_i$ ($i = 1, \ldots , n$).

Input Format

The input contains only one line with three positive integers $n, m, k$, separated by a single space.

Output Format

Output a non-negative integer, the number of schemes modulo ${10}^9+7$.

3 9 1

6

3 9 10

13

10 2000 20201003

365520548

Hint

Sample Explanation #1

The schemes that satisfy the requirements are:

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$.

Please note that the schemes in this problem are order-independent.

Sample Explanation #2

Besides the schemes in Sample #1, there are also:

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$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10$, $1\le m \le 2000$, $1\le k \le 10^9$.

Hint

Gambling is risky; it is recommended to stay away from gambling.

Before submitting, please make sure you correctly understand the constraints. If your understanding is not correct, you may get a Wrong Answer result.

Source

From the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2021).

Resources such as editorials can be found at https://github.com/yylidiw/thupc_1/tree/master.

Translated by ChatGPT 5