Congruence Equation

Description:

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$$$.

Sample Input:

2 3 5 8

Sample Output:

2

Sample Input:

4 6 7 13

Sample Output:

1

Sample Input:

233 233 10007 1

Sample Output:

1

Note:

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