\(n\)과 \(k\) (둘 다 최대 \(10^9\))와 소수 \(p\)가 주어질 때 \(\binom{n}{k} \bmod p\)를 구하시오. \(n\)이 \(p\)보다 훨씬 클 수 있으므로 뤼카 정리를 사용한다: \(n\)과 \(k\)를 \(p\)진법으로 쓰면 \(\binom{n}{k} \equiv \prod_i \binom{n_i}{k_i} \pmod p\)이며, \(n_i, k_i\)는 \(p\)진법 자릿수이다. \(k>n\)이면 값은 \(0\)이다.

한 줄에 세 정수 \(n\), \(k\), \(p\)가 주어진다 (\(0 \le n, k \le 10^9\); \(p\)는 소수, \(2 \le p \le 10^4\)).

\(\binom{n}{k} \bmod p\)을 출력한다.

riseoj 작성

출처 RiseOJ Basics