Pascal Entry Modulo a Small Prime

Row n, position k of Pascal's triangle holds C(n, k), the number of ways to choose k items from n. For a prime p, return C(n, k) mod p. The row index can be as large as 10**18, so the triangle cannot be built and the factorials cannot be formed directly. If k > n the entry is 0.

Examples

Input:  n = 5, k = 2, p = 7
Output: 3
Explanation: C(5, 2) = 10 and 10 mod 7 = 3.

Input:  n = 10, k = 3, p = 5
Output: 0
Explanation: C(10, 3) = 120 is a multiple of 5.

Constraints

• 0 <= n, k <= 10**18, p is prime, 2 <= p <= 10**5.
• Target complexity: O(p + log_p n).

Goals

• Split n and k into base-p digits
• Multiply digit-wise binomials as Lucas's theorem prescribes
• Compute small binomials mod p with factorials and inverses