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
# sys.stdin = open('in.txt', 'r')

a, b, p, x = map(int, input().split())

# A = [0, 1,   2, ..      p-2,    p-1] .. length = p
# B = [1, a, a^2, ..  a^(p-2)]         .. length = p - 1

# x * inv(x) * b = b

# a^x -> inv(a*x) * b

# 4 6 7 13
# [0, 1, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5]

# 2 3 5 8
# [0, 1, 2, 3]
# [0, 1, 2]

x += 1
res = 0

res += x//(p*(p-1)) * (p-1)
x -= x//(p*(p-1)) * (p*(p-1))

for i in range(p-1):
    ap = (pow(a, (i)*(p-2)%(p-1), p) * b) % p
    l = (x // (p-1)) + (1 if i < x%(p-1) else 0)

    if i >= ap and i-ap < l:
        res += 1
    elif i < ap and i+p-ap < l:
        res += 1
    # print(ap, l, res)

print(res)

# for i in range(1, x+1):
#     print(i*pow(a,i,p)%p, end=' ')
#     if i % (p-1) == 0:
#         print()
# print()