Problem Description

Picar and Roman, whose nationalities and ages are unknown, are playing a game of chance.

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

In each round, the gamblers participating in the game need to first select a number to bet on and pay the bet amount to the system (let's denote the currency unit used in the game as G). The chosen number can be any integer between 1 and \( n \) (where \( n \) is a fixed positive integer), with each number \( i \) corresponding to a positive integer weight \( a_i \). Let \( s = \sum_{i=1}^n a_i \), then the system selects number \( i \) with a probability of \( a_i / s \) in each round. After all gamblers have placed their bets, the system will randomly pick a number as the winning number according to the given probabilities. Gamblers who have bet on the winning number can receive a corresponding bonus based on their bet amount and the probability of the winning number, while those who bet on other numbers receive no bonus.

Regarding the bonus return rate, a natural idea is that regardless of which number a gambler bets on, the expected bonus should be equal to the bet amount. That is, if a gambler pays \( x \) G for number \( i \), then he should receive a bonus of \( sx / a_i \) if he wins.

A small flaw in this game is that the smallest denomination of currency G is 1 G, meaning the system cannot return fractional parts of the bonus. To avoid this, it is stipulated that the bet amount must be a positive integer multiple of \( k \) (where \( k \) is a fixed positive integer). The game designers need to ensure that given \( k \), \( ks \) is a positive integer multiple of each \( a_i \) (for \( i = 1, \ldots, n \)), so that no non-integer values occur when calculating the bonus.

Picar and Roman find this game interesting, and they want to play several rounds with different parameters. However, they dislike 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 schemes with the same set of weights, merely shuffling the order of weights does not significantly change the gaming experience, so Picar and Roman consider two sets of weight parameters essentially different if and only if the corresponding multisets are different. In other words, if the two sets of weight parameters \( a_1, \ldots, a_n \) and \( b_1, \ldots, b_n \) are sorted in ascending 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 of parameters are essentially different if and only if there exists an index \( i \in \{1, \ldots, n\} \) 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 provide you with \( k \), you need to ensure that in each scheme you count, \( ks \) is a positive integer multiple of each weight \( a_i \) (for \( i = 1, \ldots, n \)).

Input Format

The input consists of a single line containing three positive integers \( n, m, k \), separated by a space.

Output Format

Output a single non-negative integer, representing the number of schemes modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

3 9 1

Sample Output #1

6

Sample Input #2

3 9 10

Sample Output #2

13

Sample Input #3

10 2000 20201003

Sample Output #3

365520548

Notes

[Sample Explanation #1]

The schemes that meet 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]

In addition to the schemes in Sample #1, there are:

1. \( 5 = 1 + 2 + 2 \);
2. \( 6 = 1 + 1 + 4 \);
3. \( 7 = 1 + 1 + 5 \);
4. \( 8 = 1 + 2 + 5 \);
5. \( 9 = 1 + 2 + 6 \);
6. \( 9 = 1 + 3 + 5 \);
7. \( 9 = 2 + 2 + 5 \).

[Data Range]

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

[Hints]

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

Please ensure that you understand the data range correctly before submitting your solution. If your understanding is incorrect, you may receive a Wrong Answer verdict.

[Problem Source]

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

Solutions and other resources can be found at https://github.com/yylidiw/thupc_1/tree/master.

见题面 Input 部分

见题面 Output 部分