시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 261 48 43 25.146%

문제

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는 소수이다.

예제 입력 1

5 2 131

예제 출력 1

93

힌트

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

출처

Contest > IDTcup > 제 2회 IDTcup A번

  • 문제를 만든 사람: TAMREF