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 ≤ n ≤ x) satisfy

where a, b, p are all known constants.
Input

The only line contains four integers a, b, p, x (2 ≤ p ≤ 106 + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 1012). 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.