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.
Line 1: three space-separated integers n, r, and p.
A single integer: C(n, r) mod p.
p is prime and n < p <= 1000003Example 1
Input
5 2 101
Expected
10
Explanation
C(5,2) = 10, and 10 mod 101 = 10.
Example 2
Input
6 0 7
Expected
1
Explanation
C(6,0) = 1 for any n, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →