난수 생성기

홍준이는 통계학을 공부하다가 무작위 추출에 흥미를 느꼈다. 그는 일차 점화식으로 만들어지는 수열을 이용해 난수를 생성하려고 한다.

수열을 만들기 위해 음이 아닌 정수 m, a, c, X0이 주어진다. 수열 X_n은 다음 점화식으로 정의된다.

X_{n+1} = (aX_n + c) mod m

여기서 A mod m은 A를 m으로 나눈 나머지를 뜻한다.

최종 난수는 X_n을 양의 정수 g로 나눈 나머지이다. 따라서 생성되는 난수는 0 이상 g-1 이하의 정수이다.

주어진 값으로 X_n mod g를 구하는 프로그램을 작성하시오.

첫째 줄에 여섯 정수 m, a, c, X0, n, g가 차례대로 주어진다.

m, a, c, X0, n은 10^18 이하이고, g는 10^8 이하이다. a, c, X0는 음이 아닌 정수이며, m, n, g는 양의 정수이다.

첫째 줄에 X_n mod g의 값을 출력한다.

첫 번째 공개 테스트 케이스에서 생성되는 수열 X_n은 다음과 같다.

따라서 X_5 mod g = 8 mod 3 = 2이다.