Ceizenpok 공식

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

요약

n이 최대 10^18이고 m이 2 이상 100만 이하인 조건에서, n개 원소 집합의 k개 부분집합 수를 m으로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

i1c5l 행성의 Ceizenpok 박사는 최근 발견한 Ceizenpok 공식 덕분에 우주 전체에 이름을 알렸다. 이 공식의 인자는 $n$ , $k$ , $m$ 세 개뿐이며, 그 값은 $n$ 개의 원소로 이루어진 집합에서 $k$ 개를 고르는 조합의 수를 $m$ 으로 나눈 나머지이다.

입력

한 줄에 공백으로 구분된 정수 $n$ , $k$ , $m$ 이 주어진다. ( $1 \le n \le 10^{18}$ , $0 \le k \le n$ , $2 \le m \le 1\,000\,000$ )

출력

$n$ , $k$ , $m$ 이 주어졌을 때 공식의 값, 즉 $n$ 개 중 $k$ 개를 고르는 조합의 수를 $m$ 으로 나눈 나머지를 출력한다.

예제2

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