Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Congruence Equation

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven 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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/20/2019 19:36:19 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|