RNG 테스트

과거에는 테스트 데이터를 생성하는 데 주사위를 사용했다

평소와 마찬가지로 Forritunarkeppni Framhaldsskólanna를 위해 모든 풀이를 테스트할 수 있을 만큼 엄청난 양의 테스트 데이터를 작성해야 한다. 모든 데이터를 수작업으로 작성하는 것은 현실적이지 않으므로 KFFÍ(아이슬란드 대회 프로그래밍 협회)는 난수 생성기를 사용한다. 협회 운영진은 의심이 매우 많아서 프로그래밍 언어에 딸려 오는 구현을 신뢰하지 않는다. 따라서 Atli에게 선형 난수 생성기를 만드는 임무가 주어졌다. 하지만 Atli는 평소처럼 늦잠을 잤으므로 다른 누군가가 이 문제를 해결해야 한다. 즉, 평소처럼 바로 당신이다.

선형 난수 생성기는 세 정수 $a$, $b$, $x_0$로 정의되며, $f(x) = (ax + b)\ \%\ m$이라 하자. 퍼센트 기호는 모듈로를 나타내며, 결과를 $m$로 나눈 나머지로 계산한다는 뜻이다. 즉, 결과를 $m$로 나눌 때의 나머지를 취한다.

$n$번째 난수를 얻으려면 초깃값 $x_0$에 $f$를 $n$번 적용한다. 이는 영 번째 수가 $x_0$, 첫 번째 수가 $f(x_0)$, 그다음 수가 $f(f(x_0))$ 등임을 뜻한다.

점수

그룹 | 점수 | 해당 점수 그룹에 적용되는 입력 제한

1 | 40 | $a = 10, b = 3, m = 10^3 + 9, x_0 \leq 10^9, 1 \leq n \leq 10^6$

2 | 20 | $m = 10^5 + 3, a, b, x_0 \leq 10^9, 1 \leq n \leq 10^{18}$

3 | 20 | $m = 10^9 + 7, a, b, x_0 \leq 10^9, 1 \leq n \leq 10^{18}$

4 | 20 | $a, b, x_0, m \leq 10^9 + 7, 1 \leq n \leq 10^{18}$

입력의 유일한 줄에는 위에서 설명한 다섯 정수 $a$, $b$, $x_0$, $n$, $m$가 주어진다. 정수들은 음이 아니며, $m$는 항상 양수이다.

선형 난수 생성기가 생성하는 $n$번째 난수를 출력한다.