题意：S1=a,Sn=a*(Sn-1)^k%m,且有（a,m）=1，给出i,求Si。
思路：首先我们可以写出Sn的通项a^(1+k+k^2+...k^n-1);其次注意到m的范围是10000以内，所以我们可以利用欧拉公式降幂。
注意到（a,m）=1;又欧拉定理可知a^x%m=a^(x%phi(m))*a^phi(m)%m,而a^phi(m)=1;所以
a^x%m=a^(x%phi(m))%m;
而幂是一个等比数列，可以利用快速矩阵幂计算，算出幂之后，再利用快速幂求出答案。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=;
int euler[maxn];
ll a,k,m,n; int phi()
{
for(int i=;i<maxn;i++) euler[i]=i;
for(int i=;i<maxn;i++)
{
if(euler[i]==i)
{
for(int j=i;j<maxn;j+=i)
{
euler[j]=euler[j]/i*(i-);
}
}
}
} struct Matrix
{
ll a[][];
Matrix(){memset(a,,sizeof(a));}
Matrix operator* (const Matrix &p)
{
Matrix res;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
for(int k=;k<;k++)
{
res.a[i][j]+=(a[i][k]*p.a[k][j]%euler[m]);
}
res.a[i][j]%=euler[m];
}
}
return res;
}
}ans,base; Matrix quick_pow(Matrix base,ll n)
{
Matrix res;
for(int i=;i<;i++)
{
res.a[i][i]=;
}
while(n)
{
if(n&) res=res*base;
base=base*base;
n>>=;
}
return res;
} ll pow(ll a,ll n)
{
ll ans=;
while(n)
{
if(n&) ans=ans*a%m;
a=a*a%m;
n>>=;
}
return ans;
} void Matrix_init()
{
ans.a[][]=;
ans.a[][]=;
ans.a[][]=;
ans.a[][]=;
base.a[][]=k;
base.a[][]=;
base.a[][]=;
base.a[][]=;
} int main()
{
ll x;
phi();
while(~scanf("%lld%lld%lld%lld",&a,&k,&m,&n))
{
Matrix_init();
ans=ans*quick_pow(base,n-);
x=ans.a[][];
x=pow(a%m,x)%m;
printf("%lld\n",x);
}
return ;
}