Binomial Modulo Small Prime

Difficulty: 2100 4000 ms 128 MB

combinatorics number-theory

Compute C(N, K) modulo a prime P, where N and K are enormous (up to 10¹⁸) but P is small.

Input: one line with three integers N, K, P.

Output: C(N, K) mod P.

Constraints:

• 0 ≤ K ≤ N ≤ 10¹⁸
• 2 ≤ P ≤ 5000, P prime

Sample Tests

10 3 7

1

5 0 11

1

Read the Editorial