#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>
using namespace std;
#pragma mark - Extended Baby-Step-Gaint-Step Algorithm (exBSGS)
struct Hashtable{//Mod Based Hash Table
static const int HASHMOD = 1200611;//A Prime
long long top, hash[HASHMOD+100], value[HASHMOD+100], stk[1 << 16];
int locate(const long long x){
int h = x % HASHMOD;
while(hash[h] != -1 && hash[h] != x){
h++;
}
return h;
}
void insert(const long long key,const long long val){
int h = locate(key);
if(hash[h] == -1){
hash[h] = key;
value[h] = val;
stk[++top] = h;
}
}
long long find(const long long key){
int h = locate(key);
return (hash[h] == key)?value[h]:-1;
}
void clear(){
while(top){
hash[stk[top--]] = -1;
}
}
Hashtable(){
top = 0;
memset(hash, -1, sizeof(hash));
}
} hashtab;
struct Triple{
long long x,y,z;
Triple(const long long _x,const long long _y,const long long _z){
x = _x;
y = _y;
z = _z;
}
Triple(){
x = y = z = 0;
}
};
Triple exgcd(const long long a,const long long b){
//for inv use(A/B % C):let a = B,b = C,return.x = inv,return.z = gcd
//for solve use:return.x = specx,return.y = specy,returnz = gcd
if (b == 0) {
return Triple(1,0,a);
}
Triple last = exgcd(b, a%b);
return Triple(last.y, last.x - a / b * last.y, last.z);
}
long long exBSGS(long long A,long long B,long long C){
//A^x=B(mod C)
//Ensure B is legal
B %= C;
if (B < 0) {
B += C;
}
//Procceed A,B,C to normal BSGS if C is not prime
long long tmp = 1 % C, cnt = 0, D = 1 % C;
for (int i = 0; i < 64; i++) {
if (tmp == B) {
return i;
}
tmp = tmp * A % C;
}
for (Triple res; (res = exgcd(A, C)).z != 1; cnt++) {
if (B % res.z) {
return -1;
}
B /= res.z;
C /= res.z;
D = D * A / res.z % C;
}
//Normal BSGS
long long sqrtn = (long long)(ceil(sqrt(C)));
hashtab.clear();
long long base = 1 % C;
for (int i = 0; i < sqrtn; i++) {
hashtab.insert(base, i);
base = base * A % C;
}
long long j = -1,i = 0;
for (; i < sqrtn; i++) {
Triple res = exgcd(D, C);
long long c = C / res.z;
res.x = (res.x * B/res.z % c + c) % c;
j = hashtab.find(res.x);
if (j != -1) {
return i * sqrtn + j + cnt;
}
D = D * base % C;
}
return -1;
}
#pragma mark -
long long fastpow(long long a,long long p,long long m){
long long ret = 1;
long long fac = a;
while(p){
if(p&1){
ret *= fac;
ret %= m;
}
p >>= 1;
fac *= fac;
fac %= m;
}
return ret;
}
long long euler_phi(long long x){
long long ret = 1;
for(long long i = 2; i * i <= x; i++){
if(x % i == 0){
x /= i;
ret *= i-1;
while(x % i == 0){
x /= i;
ret *= i;
}
}
}
if(x > 1){
ret *= x-1;
}
return ret;
}
long long loop_len(long long start,long long A,long long D,long long P){
long long phi = euler_phi(P),ret = phi;
for(long long i = 2; i * i <= phi; i++){
while(phi % i == 0){
phi /= i;
}
while(ret % i == 0 && fastpow(A,start + ret/i,P) == D){
ret /= i;
}
}
if (phi > 1) {
while(ret % phi == 0 && fastpow(A,start + ret/phi,P) == D){
ret /= phi;
}
}
return ret;
}
int main(){
long long A,P,D;
unsigned long long M;
while(scanf(" %lld %lld %lld %llu",&A,&P,&D,&M) != EOF){
A %= P,D %= P;
long long first = exBSGS(A,D,P);
unsigned long long res;
long long phi = euler_phi(P);
if(first == -1 || first > M){
res = 0;
}else if(fastpow(A, first + phi, P) != D%P){
res = 1;
}else{
unsigned long long len = loop_len(first,A,D,P);
res = (M - (unsigned long long)first)/len + 1;
}
printf("%llu\n",res);
}
return 0;
}