이항 계수 4

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

요약

10^18 이하의 N, K와 2000 이하의 소수 M이 주어질 때 이항계수 C(N, K)를 M으로 나눈 나머지를 구합니다.

문제

자연수 $N$ 과 정수 $K$ 가 주어졌을 때, 이항 계수 $\binom{N}{K}$ 를 $M$ 으로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$ , $K$ , $M$ 이 공백으로 구분되어 주어진다. ( $1 \le N \le 10^{18}$ , $0 \le K \le N$ , $2 \le M \le 2000$ , $M$ 은 소수)

첫째 줄에 $\binom{N}{K}$ 를 $M$ 으로 나눈 나머지를 출력한다.