A lottery designer wants to know how many ways to choose r winning tickets out of n sold, reduced modulo a prime p (used as a checksum modulus). You are given n, r, and a prime p that is GUARANTEED to be strictly greater than n.
Compute C(n, r) mod p, the binomial coefficient 'n choose r' reduced modulo p.
Input format
Line 1: three space-separated integers n, r, and p.
Output format
A single integer: C(n, r) mod p.
Constraints
- 0 <= r <= n <= 2000
pis prime andn < p <= 1000003