시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 9 8 6 85.714%

문제

BOJ에서 어떤 문제를 풀었던 Sait2000은 입력 범위를 늘려서 장난 아니고 이산로그를 구해야 하는 문제를 만들기로 했습니다.

M = 1018 + 31은 소수이고, g = 42는 M의 원시근입니다. 즉, g1 mod M, g2 mod M ... gM - 1 mod M은 각각 서로 다른 [1; M) 범위의 정수입니다. f(x)를 gp mod M = x를 만족하는 최소의 양의 정수 p로 정의합니다. 그러면 f는 [1; M)에서 [1; M)으로 가는 전단사함수(일대일 대응)입니다.

수열 {an}을 다음과 같이 정의합니다.

  • a0 = 960002411612632915
  • ai + 1 = f(ai)

n이 주어졌을 때, an을 찾아봅시다.

입력

첫번째 줄에 정수 n이 주어집니다. (0 ≤ n ≤ 2 × 106)

출력

an을 출력합니다.

예제 입력 1

0

예제 출력 1

960002411612632915

예제 입력 2

1

예제 출력 2

836174947389522544

예제 입력 3

300300

예제 출력 3

263358264583736303

예제 입력 4

1000000

예제 출력 4

300

예제 입력 5

1000001

예제 출력 5

60615953435770536

출처