레이팅 미적용설명
\(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\)을 출력한다.
예제 1
입력
5 2 3
출력
1
예제 2
입력
10 3 7
출력
1
예제 3
입력
879378296 31182306 97
출력
15
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그