Combinatorial Divisibility

Given three integers n, m and k, consider all pairs (i, j) satisfying:

• 0 ≤ i ≤ n
• 0 ≤ j ≤ min(i, m)

For each such pair, let \(C_i^j\) denote the binomial coefficient, defined by \[ C_i^j = \frac{i!}{j!(i-j)!} \] (with the convention that \(0! = 1\)).

Your task is to count the number of pairs (i, j) for which \(C_i^j\) is a multiple of k (i.e. \(k \mid C_i^j\)). Since the answer can be large, output it modulo \(10^9+7\).

Input Format: A single line containing three integers n, m and k separated by spaces.

Output Format: A single integer representing the count of pairs \((i,j)\) for which \(k \mid C_i^j\), taken modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three space-separated integers:

• n — the upper limit for i
• m — the maximum value for j to be considered for each i (note that only j ≤ min(i, m) is considered)
• k — the divisor for which we check if \(C_i^j\) is a multiple.

outputFormat

Output a single integer, the number of pairs \((i, j)\) such that \(k\) divides \(C_i^j\), modulo \(10^9+7\).

sample

3 2 2

1