Divisible Binomial Coefficient Pairs

Given three integers n, m and k, count the number of pairs \((i,j)\) such that:

• \(0 \leq i \leq n\),
• \(0 \leq j \leq \min(i, m)\),
• \(k\) divides \(\displaystyle \binom{i}{j}\).

The binomial coefficient is defined as follows:

\[ \binom{n}{m} = \frac{n!}{m!(n-m)!}, \quad \text{where} \quad n! = 1 \times 2 \times \cdots \times n \quad \text{and} \quad 0! = 1. \]

For example, from the 3 items \(1,2,3\), choosing 2 items gives the combinations: \((1,2), (1,3), (2,3)\), and \(\binom{3}{2} = 3\).

Your task is to compute the number of pairs \((i,j)\) (with \(0\le i\le n\) and \(0\le j \le \min(i,m)\)) for which \(k\) divides \(\binom{i}{j}\). To keep the numbers manageable, you may compute binomial coefficients modulo \(k\) using the recurrence relation:

\[ \binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j} \quad (\text{with appropriate boundary conditions}). \]

inputFormat

The input consists of a single line containing three space-separated integers: n, m, and k.

outputFormat

Output a single integer: the number of pairs \((i,j)\) that satisfy the condition that k divides \(\binom{i}{j}\).

sample

2 2 2

1