Skills101
← All coding problems

nCr Modulo a Small Prime (Huge n)

hardMath & Number Theory+40 XPTime limit 2s

Compute nCr mod p where n and r can be as large as 10¹⁸ but the prime p is small. Factorials up to n are impossible to precompute here — and since n can exceed p, n! would be 0 mod p anyway, so the usual formula breaks. If r > n the answer is 0.

Input:

  • line 1: q p — the number of queries and the prime modulus
  • next q lines: two integers n r

Output: q lines — nCr mod p.

Constraints: 1 ≤ q ≤ 10⁴, 2 ≤ p ≤ 10⁵ and p is prime, 0 ≤ n, r ≤ 10¹⁸.

Think about it: Lucas' theorem. Write n and r in base p: n = n₀ + n₁p + n₂p² + …, same for r. Then nCr ≡ (n₀ C r₀) · (n₁ C r₁) · … (mod p), where any factor with rᵢ > nᵢ makes the whole answer 0. Each small nᵢ C rᵢ (with nᵢ < p) comes from factorials up to p − 1 and Fermat inverses.

Sample input 1

3 7
10 3
7 7
5 6

Sample output 1

1
1
0

Sample input 2

2 2
1000000000000000000 500000000000000000
5 1

Sample output 2

0
1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.