solution

Cho $q$ truy vấn, mỗi truy vấn gồm ba số $n, k, p$ với $p$ là số nguyên tố. Hãy tính $\binom{n}{k} \bmod p$ (tổ hợp chập $k$ của $n$ phần tử, lấy modulo $p$).

Vì $n$ có thể rất lớn, hãy dùng định lý Lucas: viết $n$ và $k$ theo cơ số $p$, khi đó $\binom{n}{k} \equiv \prod_i \binom{n_i}{k_i} \pmod{p},$ với $n_i, k_i$ là các chữ số cơ số $p$. Quy ước $\binom{n}{k} = 0$ nếu $k > n$.