1402. Choose k When the Prime Is Tiny

Answer q queries, each asking for C(n, k) modulo a prime p, where n reaches 10^18 and p is at most 1000. Print 0 when k is greater than n.

q = 4, p = 7 10 3 -> 1 since C(10, 3) = 120 and 120 = 17 * 7 + 1 10 0 -> 1 10 10 -> 1 10 11 -> 0 since k > n

The same answer through Lucas, as a check: 10 is 13 in base 7 and 3 is 03, so the product is C(1, 0) * C(3, 3) = 1 * 1 = 1.

## What most people try first

Factorial tables and one Fermat inverse, the method of problems 1326 and 1401. It fails here for two separate reasons, and both are fatal. A table up to n means 10^18 entries, which cannot be allocated. And even if it could, n is far larger than p, so n! contains p as a factor and is 0 modulo p; the inverse of 0 does not exist, and the formula gives nothing. A student who gets 0 / 0 here has not made an arithmetic slip, the method genuinely does not apply.

## Lucas' theorem

Write n and k in base p:

n = n_0 + n_1*p + n_2*p^2 + ... k = k_0 + k_1*p + k_2*p^2 + ...

Then

C(n, k) = C(n_0, k_0) * C(n_1, k_1) * C(n_2, k_2) * ... (mod p)

and the product is 0 if any digit k_i exceeds the matching n_i. Every binomial on the right has both arguments below p, so a p by p table of Pascal's triangle modulo p answers all of them, built by addition alone with no inverse anywhere.

With p at least 2 and n at most 10^18, there are at most 60 base-p digits, so each query is at most 60 table lookups.

## Why it is correct

The theorem follows from comparing coefficients in (1 + x)^n modulo p. Over the integers modulo a prime, (1 + x)^p = 1 + x^p, because every middle binomial coefficient C(p, j) for 0 < j < p has the factor p in its numerator and nothing to cancel it in the denominator. Applying that repeatedly,

(1 + x)^n = product over i of ((1 + x)^(p^i))^(n_i) = product over i of (1 + x^(p^i))^(n_i)

The coefficient of x^k on the left is C(n, k). On the right, each factor contributes a multiple of p^i to the exponent, and since base-p representation is unique the only way to reach x^k is to take k_i copies from the i-th factor. Multiplying those choices gives the product of C(n_i, k_i).

## The boundary that breaks a careless implementation

The digit loop must keep running while either n or k is non-zero, not only while n is. It must also treat the 1 % p start correctly: with p = 2 the identity element is 1, which is fine, but a constant 1 written without the reduction is wrong for any modulus that could be 1, and stating p >= 2 is what rules that out here. Finally k > n must be answered 0 before the loop, since the loop alone would compare digits and could accidentally return a non-zero product.

## Overflow

Each table entry is below p <= 1000, so the additions building the triangle reach at most 1998 and fit anywhere, including a 32-bit integer whose limit is 2147483647. The accumulator multiply acc * c[a][b] is at most 999 * 999, also small. The real width problem is the input: n reaches 10^18, so reading and dividing it needs 64 bits, and a 32-bit build answers 0 where the truth is 128. In JavaScript 10^18 is past 2^53, so n and k are BigInt and the base-p digits come out by BigInt remainder. In Java the input must not be read through StreamTokenizer, whose nval is a double and would round a value this size.

## Cost

O(p^2) once to build the triangle, then O(log n / log p) per query.

Constraints - `1 ≤ q ≤ 1000` - `0 ≤ n ≤ 1000000000000000000` - `0 ≤ k ≤ 1000000000000000000` - `2 ≤ p ≤ 1000` and `p` is prime