N!!!...! mod P
시간 제한1초메모리 제한1024 MB
N, K와 소수 P가 주어질 때 a_0 = N, a_{n+1} = (a_n)!으로 정의된 수열의 a_K를 P로 나눈 나머지를 구한다. N, K, P는 최대 5×10^8이다.
문제
Baekjoon Online Judge의 쉬운 문제 N! mod P (3) 를 해결하지 못해 실의에 빠진 메시는 더욱 어려운 문제를 만들어 "나만 해결한 문제"를 추가하려고 한다. 메시가 내려는 문제는 이름부터 K배나 강력한 N!!!....! mod P 로, 다음의 값을 구하는 문제이다.
자연수 N, K와 소수 P가 주어질 때 (( ... (N!)! ... )!)! mod P를 구하시오. (!는 총 K개이다.)
메시의 문제를 엄밀하게 표현하면, a0 = N, an+1 = (an)! (n ≥ 0) 으로 정의된 수열에서 aK mod P를 구하는 문제가 된다. 하지만 듀벤은 이 문제가 공개되자마자 해결해 버리고, 숏코딩까지 시전하여 메시에게 큰 충격을 안겨주었다.
메시는 N! mod P (3) 의 모범 코드를 블로그에서 베껴서 데이터를 만들었기 때문에 이 문제를 해결할 줄 모른다. 메시를 위해 이 문제를 해결해 주자.
입력
1번째 줄에 자연수 N, K와 소수 P가 공백을 사이에 두고 주어진다.
출력
메시의 문제에 대한 답, 즉 (( ... (N!)! ... )!)! mod P 를 출력한다.
제한
- 2 ≤ N, K, P ≤ 5 × 108
- P는 소수이다.
힌트
- 출제자가 의도하고, 작성한 풀이는 600ms 안에 동작합니다.