今天欧拉降幂，怎么操作姿势都不对。。。。。
例题：
The Preliminary Contest for ICPC Asia Nanjing 2019：
B super_log：
求 b 个 a ^ a ^ a ^ a ^ a ^ a ^ a :
很明显就是欧拉降幂：


然而就这破题。。卡了我20多发。

贴上代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn=1001000;
const int mod=1e9+7;
int p[maxn],prime[maxn];
bool ha[maxn];
int cnt=0;

void Prime(void)
{
    p[1]=1;
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
        {
            prime[cnt++]=i;
            p[i]=i-1;
        }
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                p[i*prime[j]]=p[i]*prime[j];
                break;
            }
            p[i*prime[j]]=p[i]*p[prime[j]];
        }
    }
}

ll mypow(ll a,ll b,ll mod)
{

    ll ans=1;
    if(a>=mod) a=a%mod+mod;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a;
            if(ans>=mod) ans=ans%mod+mod;
        }
        //a也要像ans一样判断，因为a对最终答案是有贡献的。
        a=a*a;
        if(a>=mod) a=a%mod+mod;
        b>>=1;
    }
    return ans;
}



ll a,b,m;


ll dfs(ll pm,ll cnt)
{
    if(cnt==0) return 1%pm;
    if(a%pm==0) return pm;
    return mypow(a,dfs(p[pm],cnt-1),pm);
}

int main(void)
{
    Prime();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&a,&b,&m);

        printf("%lld\n",dfs(m,b)%m);
    }
    return 0;
}