P7607 [THUPC 2021] Gambler Problem

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

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

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

**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](https://github.com/yylidiw/thupc_1/tree/master). Translated by ChatGPT 5