Ceizenpok’s formula

시간 제한1초메모리 제한1024 MB

요약

n이 10^18까지 커질 수 있고 m이 합성수일 때 C(n, k) mod m을 계산한다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

Dr. Ceizenpok from planet i1c5l became famous across the whole Universe thanks to his recent discovery --- the Ceizenpok’s formula. This formula has only three arguments: $n$ , $k$ and $m$ , and its value is a number of $k$ -combinations of a set of $n$ modulo $m$ .

While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

입력

Single line contains three integers $n$ , $k$ , $m$ , separated with spaces ( $1 \le n \le 10^{18}$ , $0 \le k \le n$ , $2 \le m \le 1\\,000\\,000$ ).

출력

Write the formula value for given arguments $n$ , $k$ , $m$ .

예제2

예제 1
입력
```
2 1 3
```
예상 출력
```
2
```
예제 2
입력
```
4 2 5
```
예상 출력
```
1
```