1326. Choose k, Modulo a Prime
Print the number of ways to choose k items from n, modulo a prime p.
Print 0 when k is greater than n.
You are guaranteed n < p.
The value itself is astronomically large, so it never exists in full. Everything
happens modulo p, and the formula has a division:
C(n, k) = n! / (k! * (n - k)!)
Division is the whole difficulty. There is no integer division modulo p, and
dividing first and reducing afterwards is impossible because the numerator does
not fit anywhere.
Instead multiply by the modular inverse. Since p is prime and none of these
factorials is a multiple of it, Fermat's little theorem gives the inverse
directly as x^(p-2) mod p, computed by fast exponentiation in O(log p) steps.
The guarantee that n < p is what makes this work at all. If n reached p,
then n! would contain p as a factor and be 0 modulo p, the inverse would
not exist, and the answer would need Lucas' theorem instead.
Precompute the factorials once up to n. Calling fast exponentiation inside the
loop instead turns O(n) into O(n log p) for no reason.
Constraints - `0 ≤ n < p` - `0 ≤ k ≤ 1000000` - `2 ≤ p ≤ 1000000007`, and `p` is prime - `n ≤ 1000000`
Input
One line containing three integers n, k and p.
Output
Print the number of ways to choose k from n, modulo p.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.