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.
The only line contains four integers $a,b,p,x$ ($2 \leq p \leq 10^6+3$, $1 \leq a,b &lt; p$, $1 \leq x \leq 10^{12}$). It is guaranteed that $p$ is a prime.
In the first sample, we can see that $n=2$ and $n=8$ are possible answers.
2 3 5 8
2
4 6 7 13
1
233 233 10007 1
1
338792 190248 339821 152634074578
449263
629260 663548 739463 321804928248
434818
656229 20757 818339 523535590429
639482
1000002 1000002 1000003 1000000000000
999998
345 2746 1000003 5000000
4
802942 824238 836833 605503824329
723664
1 1 2 880336470888
440168235444
2 2 3 291982585081
97327528361
699601 39672 1000003 391631540387
391905
9 1 11 792412106895
72037464262
85 535 541 680776274925
1258366493
3153 4504 7919 903755230811
114124839
10021 18448 20719 509684975746
24599907
66634 64950 66889 215112576953
3215965
585128 179390 836839 556227387547
664796
299973 381004 1000003 140225320941
140481
941641 359143 1000003 851964325687
851984
500719 741769 1000003 596263138944
596056
142385 83099 1000003 308002143690
307937
891986 300056 999983 445202944465
445451
620328 378284 999983 189501757723
189574
524578 993938 999979 535629124351
535377
419620 683571 999979 243073161801
243611
339138 549930 999883 962863668031
962803
981603 635385 999233 143056117417
143126
416133 340425 998561 195227456237
195090
603835 578057 996323 932597132292
936103
997998 999323 1000003 999968459613
999964
997642 996418 999983 999997055535
1000007
812415 818711 820231 999990437063
1219017
994574 993183 1000003 999974679059
999965
999183 998981 999979 999970875649
999996
1 1 2 1
1
699601 39672 1000003 1
0
4 1 5 15
2
912896 91931 999983 236754
1
154814 35966 269041 1234567
4
1 2 5 470854713201
94170942640
3 27 29 968042258975
33380767549
473 392 541 108827666667
201160200
8 27 29 193012366642
6655598851
1302 504 1987 842777827450
424145863
693528 398514 1000003 1000000000000
999995
533806 514846 1000003 999999999999
999997
812509 699256 1000003 999999999999
999997
28361 465012 1000003 1000000000000
999996
28361 465012 1000003 12693229
1
28361 465012 1000003 13271836
2
28361 465012 1000003 13271835
1
28361 465012 1000003 13421000
4
28361 465012 1000003 19609900
9
28361 465012 1000003 12693228
0
1 1 2 1000000000000
500000000000
1 1000002 1000003 1000000000000
999997
1 44444 1000003 999999999998
999997
2 1000002 1000003 1000000000000
1000001
2 23333 1000003 1000000000000
999999
import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))

def gcd2(a, b):
    """a*x + b*y = gcd(a,b)なるx,yも求める
    """
    l = []
    while b:
        l.append(divmod(a,b))
        a, b = b, a%b
    x, y = 1, 0
    for aa,bb in l[::-1]:
        x, y = y, x - aa*y
    return a, x, y

def modinv(x, M):
    """素数ではないM、Mと互いに素なxに対し
    x * y == 1 mod M なるyを求める
    """
    a,xx,yy = gcd2(x,M)
    return a,xx%M

def solve(a,b,n):
    """a*x = b mod nを解く
    """
    g,xx,yy = gcd2(a,n)
    if b%g!=0:
        return None
    a //= g
    n //= g
    b //= g
    # aとnが互いに素になっているので
    ainv = modinv(a, n)[1]
    x = ainv*b%n
    return x

def crt(rs, ms):
    """中国剰余定理
    x == rs[i] mod ms[i] をみたすxをを求め、(x, l(=ms))を返す
    (そのようなxは x + i * lとして書ける)
    存在しない場合はNoneを返す
    長さが0の配列を渡すと(0,1)を返す
    """
    r0 = 0
    m0 = 1
    for r1,m1 in zip(rs, ms):
        if m0<m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        if m0%m1==0:
            if r0%m1 != r1:
                return None,None
            else:
                continue
#         print(m0,m1)
        g,im = modinv(m0, m1)
        u1 = m1//g
        if (r1-r0)%g!=0:
            return None,None
        x = (r1-r0) // g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0<0:
            r0 += m0
    return r0,m0

a,b,p,x = list(map(int, input().split()))
### 素数の逆元とCombination

M = p # 出力の制限
N = p+10 # 必要なテーブルサイズ
inverse = [0] * (N+1) #逆元テーブル計算用テーブル
inverse[0], inverse[1] = [0, 1] 
for i in range( 2, N + 1 ):
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
c = 1
index = [[] for _ in range(p)] # index[i]: a^x = i mod p となる 0<=x<p-1 のリスト
for i in range(p-1):
    index[c].append(i)
    c *= a
    c %= p
ans = 0
for i in range(1,p):
    j = b*inverse[i]%p
    for jj in index[j]:
        res = crt((i, jj), (p, p-1))
        if res[0] is not None:
            r,m = res
#             print(res)
            ans += max(0, x-r+m)//m
print(ans)