개구리들 Batch Compilation commands

각 $i \ge 0$에 대해, $i번 격자의 아름다움은 $x^{i} \mod p$와 같습니다.

초기에 $k$마리의 똑똑한 개구리들 ($1$부터 $k$까지의 번호가 붙어 있음)이 $0$번 격자에 서 있고, 각 개구리의 행복 지수는 1입니다. 승현이는 이 개구리들이 아래와 같은 단계에 따라 움직인다는 것을 알아냈습니다.

1. 1번 개구리가 한 격자 앞으로 움직이고, 그의 행복 지수는 그가 들어간 격자의 아름다움만큼 증가합니다.
2. 각 $i \ge 2$에 대해, 만약 $i-1$번 개구리가 움직이고 $i-1$번 개구리의 행복 지수가 $m$의 배수라면, $i$번 개구리는 한 격자 앞으로 움직이고 $i$번 개구리의 행복 지수는 그가 들어간 격자의 아름다움만큼 증가할 것입니다.
3. $1$번 개구리와 $k$번 개구리 사이의 거리가 $d$ 이상이라면, 더 이상 움직이지 않습니다. 그렇지 않다면, 개구리들은 다시 1번 과정으로 돌아가 움직일 것입니다.

개구리들이 움직임을 멈췄을 때 1번 개구리의 위치를 계산하세요.

입력 형식

5개의 정수 $x$ ($1 \le x \le p-1$), $p$ ($2 \le p \le 10^{5}$), $k$ ($2 \le k \le 10$), $m$ ($2 \le m \le 10$)과 $d$ ($1 \le d \le 10^{12}$가 주어집니다. $p$는 소수임이 보장됩니다.

출력 형식

개구리들이 움직임을 멈췄을 때 1번 개구리의 위치를 출력합니다.

예제

예제 1

입력

1 2 3 2 10

출력

14

예제 2

입력

58 10007 10 10 123456789012

출력

123456789143