Congruence Equation
Description
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.
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.
Print a single integer: the number of possible answers $n$.
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$.
Samples
2 3 5 8
2
4 6 7 13
1
233 233 10007 1
1
Note
In the first sample, we can see that $n=2$ and $n=8$ are possible answers.