Frogs
Before the Olympics began, the jury members were taken on a tour to see a waterfall. Unfortunately, the waterfall was closed for maintenance. Meanwhile, the zebra named Hippo decided to explore the area on her own and arrived at the renowned Long Barrier Swamp.
The swamp consists of an infinitely long sequence of hummocks, each numbered with consecutive non-negative integers. For each hummock i (where i ≥ 0), its height is determined by the remainder when x^i is divided by p.
Initially, there are k frogs, numbered consecutively from 1 to k, all starting on hummock 0. Each frog begins with a fatigue level of 1. Hippo observed that the frogs move according to the following rules:
Frog number 1 moves forward by one hummock, and its fatigue increases by the height of the new hummock.
Each subsequent frog, starting from the second one, moves forward by one hummock if the frog before it also moved and if the fatigue of the preceding frog is divisible by m. In this case, the moving frog's fatigue increases by the height of the hummock it lands on. If these conditions are not met, the frog stays in place and its fatigue remains unchanged.
The frogs stop moving if the distance between the first and the k-th frog is at least d. If not, the process repeats starting from the first frog.
Determine the hummock number where the first frog will be when the frogs stop moving.
Input
The input consists of five integers: x (1 ≤ x ≤ p-1), p (2 ≤ p ≤ 10^5), k (2 ≤ k ≤ 10), m (2 ≤ m ≤ 10), and d (1 ≤ d ≤ 10^12).
It is guaranteed that p is a prime number.
Output
Output the number of the hummock where the first frog will be when the frogs stop moving.