18373번 - N!!!...! mod P

Baekjoon Online Judge의 쉬운 문제 N! mod P (3) 를 해결하지 못해 실의에 빠진 메시는 더욱 어려운 문제를 만들어 "나만 해결한 문제"를 추가하려고 한다. 메시가 내려는 문제는 이름부터 K배나 강력한 N!!!....! mod P 로, 다음의 값을 구하는 문제이다.

자연수 N, K와 소수 P가 주어질 때 (( ... (N!)! ... )!)! mod P를 구하시오. (!는 총 K개이다.)

메시의 문제를 엄밀하게 표현하면, a₀ = N, a_n+1 = (a_n)! (n ≥ 0) 으로 정의된 수열에서 a_K mod P를 구하는 문제가 된다. 하지만 듀벤은 이 문제가 공개되자마자 해결해 버리고, 숏코딩까지 시전하여 메시에게 큰 충격을 안겨주었다.

메시는 N! mod P (3) 의 모범 코드를 블로그에서 베껴서 데이터를 만들었기 때문에 이 문제를 해결할 줄 모른다. 메시를 위해 이 문제를 해결해 주자.

1번째 줄에 자연수 N, K와 소수 P가 공백을 사이에 두고 주어진다.

메시의 문제에 대한 답, 즉 (( ... (N!)! ... )!)! mod P 를 출력한다.

• 2 ≤ N, K, P ≤ 5 × 10⁸
• P는 소수이다.

• 출제자가 의도하고, 작성한 풀이는 600ms 안에 동작합니다.