이산로그가 장난이냐?

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

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

수열 {a**n}을 다음과 같이 정의합니다.

• a0 = 960002411612632915
• a**i + 1 = f(a**i)

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

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

a**n을 출력합니다.