Counting Zero Binomial Coefficients

Given three integers n, m, and a prime number k, count the number of pairs \((i, j)\) satisfying:

• \(1 \leq i \leq n\)
• \(0 \leq j \\leq \min(i, m)\)
• \({i \choose j} \equiv 0 \pmod{k}\)

Here, \({i \choose j}\) denotes the binomial coefficient (the number of ways to choose j elements from a set of i distinct elements). The answer is the total count of such pairs \((i, j)\).

Note: Since k is prime, properties from Lucas' theorem can be used to analyze the divisibility, though a direct computation based on dynamic programming of Pascal's triangle modulo k is sufficient for moderate input sizes.

inputFormat

The input consists of a single line containing three integers n, m, and k separated by spaces.

\(1 \leq n\), \(0 \leq m\) and k is a prime number.

outputFormat

Output one integer: the number of pairs \((i,j)\) satisfying the given conditions.

sample

3 3 2

1