21864번 - 이산로그가 장난이냐?

문제

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

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

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

• a₀ = 960002411612632915
• a_{i + 1} = f(a_i)

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

입력

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

출력

a_n을 출력합니다.

제한

힌트