The gamblers Picar and Roman, whose nationalities and ages are unknown, are playing a game.

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

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

Regarding the payout ratio, a natural idea is: regardless of which number a gambler bets on, the expected payout should be equal to the amount bet. That is, if a gambler pays $x$ G for number $i$, they should receive $sx/a_i$ as a payout if they win.

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

Picar and Roman find this game interesting and hope to play a few rounds with different parameters. However, they dislike 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 sets of weights that are the same, simply shuffling the order of weights does not change the game experience significantly. Therefore, Picar and Roman consider two sets of weight parameters to be essentially different if and only if their corresponding multisets are different. In other words, if two sets of weight parameters $a_1, \dots, a_n$ and $b_1, \dots, b_n$ are sorted in non-decreasing order to obtain $1 \le \alpha_1 \le \alpha_2 \le \dots \le \alpha_n$ and $1 \le \beta_1 \le \beta_2 \le \dots \le \beta_n$, then these two sets of parameters are essentially different if and only if there exists an index $i \in \{1, \dots, 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 gave you $k$, you must ensure that for every scheme you count, $ks$ is a positive integer multiple of each weight $a_i$ ($i=1, \dots, n$).

Input

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

Output

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

Examples

Input 1

3 9 1

Output 1

6

Note 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 order of weights in the schemes does not matter.

Input 2

3 9 10

Output 2

13

Note 2

In addition to the schemes in Example 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$.

Input 3

10 2000 20201003

Output 3

365520548

Subtasks

For $100\%$ of the data, $1 \le n \le 10$, $1 \le m \le 2000$, $1 \le k \le 10^9$.

Note

Gambling carries risks; it is recommended to stay away from gambling.

Please confirm your understanding of the data range before submitting. If your understanding is incorrect, you may receive a Wrong Answer result.