Counting Valid Gambling Game Configurations

Two gamblers, Picar and Roman, are playing a random betting game. In each round, the players choose a number and place a bet in units of G. There are n betting numbers, and each number i is associated with a positive integer weight a_i (with 1 ≤ a_i ≤ m). Let \( s=\sum_{i=1}^n a_i \) be the sum of all weights. The system draws a winning number \( i \) with probability \(\frac{a_i}{s}\). If a gambler bets x G on number i, then, upon winning, they receive a bonus of \(\frac{s\,x}{a_i}\;G\). To guarantee that the bonus is an integer (since the smallest currency unit is 1 G), it is required that every bet is a positive integer multiple of a given integer k and that for every weight a_i the value \(k\cdot s\) is an integer multiple of a_i, i.e.,

[ a_i\mid k\cdot s,\quad \text{for } i=1,2,\ldots,n. ]

Furthermore, the sum \( s \) cannot exceed a given positive integer m (hence each weight is at most m). Two weight configurations are considered essentially different only if their multisets of weights differ. In other words, if the sorted sequences are \(\alpha_1 \le \alpha_2 \le \cdots \le \alpha_n\) and \(\beta_1 \le \beta_2 \le \cdots \le \beta_n\), they are different if there exists an index i such that \(\alpha_i \neq \beta_i\).

Your task is to count the number of essentially different weight configurations (multisets) for given values of n, m, and k that satisfy the above requirements. Note that the divisibility condition \(a_i\mid k\cdot s\) for each chosen a_i can be reinterpreted as requiring that for each a in the multiset, if we define

[ \ell(a)=\frac{a}{\gcd(a,k)}, ]

then if we let

[ L = \operatorname{lcm}\Big(\ell(a_1), \ell(a_2), \dots, \ell(a_n)\Big), ]

the final sum ( s ) must be divisible by (L) and also (s \le m).

inputFormat

The input consists of a single line containing three space‐separated positive integers: n (the number of betting numbers), m (the upper bound for the sum of weights, as well as for each individual weight), and k (the bet unit divisor).

outputFormat

Output a single integer representing the number of essentially different valid configurations.

sample

2 10 1

5