↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
long long add(long long i,long long j,long long mod)↵
{↵
if(i+j<0)↵
{↵
int tmp=0;↵
while(i+j+tmp<0)tmp+=mod;↵
return i+j+tmp;↵
}↵
if(i+j>=mod)↵
{↵
int tmp=0;↵
while(i+j-tmp>=mod)tmp+=mod;↵
return i+j-tmp;↵
}↵
return i+j;↵
}↵
long long power(long long n,long long k,long long mod)↵
{↵
n%=mod;↵
long long rez=1;↵
while(k)↵
{↵
if(k&1)↵
{↵
rez=(rez*n)%mod;↵
}↵
n=(n*n)%mod;↵
k>>=1;↵
}↵
return rez;↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
long long x,a,n,c;↵
cin >> x >> a >> n >> c;↵
while(x!=0 || a!=0 || n!=0 || c!=0)↵
{↵
if(a%c!=1)↵
{↵
long long rez=power(a,n,c);↵
rez=(rez*x)%c;↵
long long sub=power(a,n,c);↵
sub=add(sub,-1,c);↵
long long temp=add(a,-1,c);↵
long long inverse=power(temp,add(c,-2,c),c);↵
sub=(sub*a)%c;↵
sub=(sub*inverse)%c;↵
rez=add(rez,-sub,c);↵
cout << rez << '\n';↵
cin >> x >> a >> n >> c;↵
}↵
else↵
{↵
x=add(x,-n,c);↵
cout << x <<'\n';↵
cin >> x >> a >> n >> c;↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
↵
