Problem: Given an integer x. Your task is to find out how many positive integers n (1 ≤ n ≤ x) satisfy $$$n ⋅ a^n ≡ b   (mod\;p), where a, b, p$$$ are all known constants.

Input

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

Solution (in PYTHON3):

Solution:
import sys
ints = (int(x) for x in sys.stdin.read().split())

a,b,p,x = (next(ints) for i in range(4))

def ext_gcd(a, b):
  """return (g, x, y) such that a*x + b*y = g = gcd(a, b) and abs(x)<=b+1 ans abs(y)<=a+1"""
  x, x1, y, y1 = 0, 1, 1, 0
  while a != 0:
   (q, a), b = divmod(b, a), a
   y, y1 = y1, y - q * y1
   x, x1 = x1, x - q * x1
  return b, x, y

def mod_inv(a, mod):
  """return x such that (x * a) % mod = gcd(a, mod)"""
  g, x, y = ext_gcd(a, mod)
  return x % mod


ans, x = divmod(x, (p-1)*p)
ans = (p-1)*ans-(b==0)
an = 1
for i in range(p-1):
  k = (mod_inv((an*(p-1))%p, p)*(b-i*an)) % p
  ans += k*(p-1)+i<=x
  an = (an*a)%p
print(ans)

if 0:
  a, b, p = 2, 1, 5
  for k in range(p+1):
    h = [((k*(p-1)+i)*(a**i))%p for i in range(0, p-1)]
    print(*h)