408840: GYM103347 J Rosencrantz and Guildenstern

J. Rosencrantz and Guildensterntime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Hamlet is particularly annoyed with his treacherous 'friends' Rosencrantz and Guildenstern and as they set off on their journey to England, he decides to hand them a challenge that they must solve correctly in order to be welcome back in Denmark. Hamlet, ever a scholar of the math and sciences, decides that he wants to know how many values of $$$k$$$ satisfy the equation:

$$$k \cdot x^{k} \equiv y \pmod{p}$$$ Hamlet quickly realizes that this problem can have an infinite number of solutions so he wants the number of values of $$$k$$$ between $$$1$$$ and $$$a$$$ respectively for some large integer $$$a$$$. He still can't figure out the exact answer and wants to be prepared when Rosencrantz and Guildenstern return so he asks you to compute this answer for you.Input

The first and only line contains four space-separated integers $$$p, x, y, a$$$ where $$$p$$$ is guaranteed to be a prime, $$$2 \leq p \leq 10^{6} + 3$$$, $$$1 \leq x, y, \leq p - 1$$$, and $$$1 \leq a \leq 10^{12}$$$.

Output

Output a single answer representing the number of possible values $$$k$$$ which satisfy the puzzle.

ExamplesInput

5 2 3 10

Output

3

Input

7 4 6 13

Output

1

Note

In the first test case, we see that $$$k = 2$$$, $$$k = 8$$$ and $$$k = 9$$$ are valid assignments to satisfy the equation.