Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

E. Congruence Equation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$x$$$. Your task is to find out how many positive integers $$$n$$$ ($$$1 \leq n \leq x$$$) satisfy $$$$$$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$$$$$ where $$$a, b, p$$$ are all known constants.

Input

The only line contains four integers $$$a,b,p,x$$$ ($$$2 \leq p \leq 10^6+3$$$, $$$1 \leq a,b < p$$$, $$$1 \leq x \leq 10^{12}$$$). It is guaranteed that $$$p$$$ is a prime.

Output

Print a single integer: the number of possible answers $$$n$$$.

Examples
Input
2 3 5 8
Output
2
Input
4 6 7 13
Output
1
Input
233 233 10007 1
Output
1
Note

In the first sample, we can see that $$$n=2$$$ and $$$n=8$$$ are possible answers.