Given 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.

Difficulty: interview

Starter code:

Solutions:
a, b, p, x = [int(x) for x in input().split()]

powers = [a]

while powers[-1] != 1:
    powers.append(powers[-1] * a % p)
    
order = len(powers)
powers = [powers[-1]] + powers

inverse = pow(order, p-2, p)

def f(sol):
    return (x // (p * order)) + (1 if sol <= x % (p * order) else 0)

def chinese(a, n, b, m):
    k = inverse * (b - a + m) % m
    x = k * n + a
    return x % (n * m)

res = 0
for i in range(len(powers)-1):
    inv = powers[order - i]
    val = inv * b % p
    
    sol = chinese(i, order, val, p)
    
    res += f(sol)
    
print(res)


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


def brute(a,b,p,x):
    for n in range(1, x+1):
        if (n*pow(a,n,p)) % p == b:
            print(n)

#brute(a,b,p,x)

sols = 0

inva = pow(a,p-2,p)

##print('a', inva)

a2 = 1
b2 = b
s = 0
d1 = -b
fac = p*(p-1)
while s < p-1:
    k = (d1 + s) % p
    u = k
    L = x - s - (p-1)*k
    sols += L//fac + 1
##    while (p-1)*u + s <= x:
##        n = (p-1)*u + s
##        print(s, k, n)
##        print(n)
##        #print(n*pow(a,n,p) % p, b)
##        sols += 1
##        u += p
    d1 = (d1 * inva) % p
    s += 1

print(sols)
        

        
    



a, b, p, x = list(map(int, input().split()))
ans = 0
ainv = 1
for i in range(p - 2):
    ainv = (ainv * a) % p
rem = 1
inv = 1
lcm = p * (p - 1)
for n in range(1, p):
    rem = (rem * a) % p
    inv = (inv * ainv) % p
    i0 = min(p, ((n * rem - b) * inv + p) % p)
    n0 = n + i0 * (p - 1)
    ans += max(0, (x - n0 + lcm) // lcm)
print(ans)


# -*- coding: utf - 8 -*-
"""""""""""""""""""""""""""""""""""""""""""""
|    author: mr.math - Hakimov Rahimjon     |
|    e-mail: mr.math0777@gmail.com          |
|    created: 04.02.2018 13:31              |
"""""""""""""""""""""""""""""""""""""""""""""
# inp = open("input.txt", "r"); input = inp.readline; out = open("output.txt", "w"); print = out.write
TN = 1


# ===========================================


def solution():
    a, b, p, x = list(map(int, input().split()))
    ans = 0
    ainv = 1
    for i in range(p - 2):
        ainv = (ainv * a) % p
    rem = 1
    inv = 1
    lcm = p * (p - 1)
    for n in range(1, p):
        rem = (rem * a) % p
        inv = (inv * ainv) % p
        i0 = min(p, ((n * rem - b) * inv + p) % p)
        n0 = n + i0 * (p - 1)
        ans += max(0, (x - n0 + lcm) // lcm)
    print(ans)


# ===========================================
while TN != 0:
    solution()
    TN -= 1
# ===========================================
# inp.close()
# out.close()


# -*- coding: utf - 8 -*-
"""""""""""""""""""""""""""""""""""""""""""""
|    author: mr.math - Hakimov Rahimjon     |
|    e-mail: mr.math0777@gmail.com          |
|    created: 04.02.2018 13:31              |
"""""""""""""""""""""""""""""""""""""""""""""
# inp = open("input.txt", "r"); input = inp.readline; out = open("output.txt", "w"); print = out.write
TN = 1


# ===========================================


def solution():
    a, b, p, x = list(map(int, input().split()))
    ans = 0
    ainv = 1
    for i in range(p - 2):
        ainv = (ainv * a) % p
    rem = 1
    inv = 1
    lcm = p * (p - 1)
    for n in range(1, p):
        rem = (rem * a) % p
        inv = (inv * ainv) % p
        i0 = min(p, ((n * rem - b) * inv + p) % p)
        n0 = n + i0 * (p - 1)
        ans += max(0, (x - n0 + lcm) // lcm)
    print(ans)


# ===========================================
while TN != 0:
    solution()
    TN -= 1
# ===========================================
# inp.close()
# out.close()


a,b,p,x = [int(x) for x in input().split()]

ainv = pow(a,p-2,p)

count = 0

n = 1
exp = ainv*b%p
while n<p:
    m = n
    if exp>n:
        m += (n+p-exp)*(p-1)
    else:
        m += (n-exp)*(p-1)
    
    if m<=x: count += 1 + (x-m)//(p*(p-1))
    
    n += 1
    exp = (exp*ainv)%p

print(count)

def congr(a, b, p, x):
    solutions = 0
    power = pow(a, p - 2, p)
    a2, b2, s, d1 = 1, b, 0, -b
    prod = p * (p - 1)
    while s < p - 1:
        k = (d1 + s) % p
        L = x - s - (p - 1) * k
        solutions += L // prod + 1
        d1 = (d1 * power) % p
        s += 1
    return solutions


a, b, p, x = [int(j) for j in input().split()]
print(congr(a, b, p, x))


def AC():
    a, b, p, x = map(int, input().split())
    ans = 0
    m = 1
    for i in range(p - 2):
        m = (m * a) % p
    rem = 1
    inv = 1
    Ch = p * (p - 1)
    for n in range(1, p):
        rem = (rem * a) % p
        inv = (inv * m) % p
        cur = min(p, ((n * rem - b) * inv + p) % p)
        rep = n + cur * (p - 1)
        ans += max(0, (x - rep + Ch) // Ch)
    print(ans)
AC()

import sys

def calc(a, b, p, x):
    ans = 0
    power = pow(a, p - 2, p)
    a2, b2, s, d1 = 1, b, 0, -b
    prod = p * (p - 1)
    while s < p - 1:
        k = (d1 + s) % p
        L = x - s - (p - 1) * k
        ans += L // prod + 1
        d1 = (d1 * power) % p
        s += 1
    return str(ans)
 
 
a, b, p, x = list(map(int,sys.stdin.readline().split()))
sys.stdout.write(calc(a, b, p, x))