题目链接：https://nanti.jisuanke.com/t/17414

互质的时候欧拉定理咋怎都对
但是不互质的时候欧拉定理一直感觉有点怪，不知道为什么，证明也看不懂，写一个目前来说还算正确的：

a b % n = a b <mtext>   </mtext> <mtext>   </mtext> <mtext>   </mtext> <mtext>   </mtext> <mtext>   </mtext> ( b < n 的 时 候 ， 而 且 不 能 加 φ ( n ) , 加 了 反 而 是 错 的 )

a b % n = a b % φ ( n ) + φ ( n ) <mtext>   </mtext> <mtext>   </mtext> <mtext>   </mtext> <mtext>   </mtext> <mtext>   </mtext> ( 这 个 时 候 就 要 加 φ ( n ) 了 ， 不 加 就 会 错 )

这道题我们不好判断指数与模数谁大，到底加不加 φ ( m o d ) ，但是我们阔以发现当 n = 4 的时候就已经很大了为 262144 ，而 1 e 9 以内应该是找不到一个不互质的 φ ( n ) 比 262144 还大（不知道能不能找到，反正是过题了。。。），所以 n >= 5 的时候都采用第二种

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int a[5]={0,1,2,9,(1<<18)};
LL ksm(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1)res=(res*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}
LL Phi(LL n)
{
    LL res=n;
    for(LL i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)res=res/n*(n-1);
    return res;
}
LL dfs(LL n,LL m)
{
    if(m==1)return 0;   //模数是1答案肯定是0 
    int t=Phi(m);
    if(n<=4)return a[n]%m; //特判 
    LL res=dfs(n-1,t);
    return ksm(n,res%t+t,m);//因为之后的指数肯定都是大于1e9的，所以肯定是要加上phi(p)的 

}
int main()
{
    LL N,M;
    while(cin>>N>>M)cout<<dfs(N,M)<<endl;
}