갓 소수
시간 제한2초메모리 제한512 MB
고정된 a, b와 키파가 가장 좋아하는 소수 p를 계수로 하는 LCG를 n에서 출발해 p번 반복하고 x_p를 출력한다.
문제
키파는 소수를 좋아한다. 키파가 제일 좋아하는 소수를 p라 하자. a = 860798509, b = 198609463, N = p, x0 = n으로 LCG를 돌려서 xp의 값을 출력하라.
LCG(Linear Congruential Generator)의 정의는 다음과 같은 수열 {xi}이다: 모든 자연수 k에 대해,
xk = axk-1 + b (mod N), 0 ≤ xk < N.
LCG는 다양한 곳에서 사용되는데, 예를 들어 C의 rand(), Java의 Random.nextInt(), 그리고 제1회 구데기컵의 이 문제가 있다.
입력
n이 주어진다. int 범위임이 보장된다.
출력
문제에 해당하는 답을 출력한다.