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 PYTHON):

Solution:
def pow_mod(a,sup,m):
	ans = 1
	while sup > 0:
		if sup & 1: ans = (ans*a) % m
		a = a*a % m
		sup >>= 1
	return ans

a, b, p, x = [int(t) for t in raw_input().split()]
inv = [0] * p	
ans = 0
pp = p*(p-1)
for i in xrange(1,p):
	w = pow_mod(a,i,p)
	r, s = (p-1)*w%p, (b-i*w)%p
	if r == 0:
		if s: 
			ans += x/(p-1)
			if x%(p-1)>=i:
				ans += 1
		#print i, ans, r, s, 'a'
		break
	if not inv[r]:
		inv[r] = pow_mod(r, p-2, p)
		inv[inv[r]] = r
	k = s*inv[r]%p
	y = x-i-k*(p-1)
	if y >= 0:
		ans += y/pp+1
	#print i, ans, r, s, 'b', k
print ans