int  pow_mod(LL a,LL b)
{
    int num=1;
    while(b)
    {
        if(b&1)   num=(num*a)%MOD;  
        a=(a*a)%MOD;
        b>>=1;
    }
    return num;
}

bool  flag[maxn]={0};
void Prime(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(flag[i]) continue;
         prime[cnt++]=i;
        for(int j=2;i*j<=x;j++)
            flag[i*j]=1;
    }
}

 for(int i=2;i<=n;i++)   phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
        if(!phi[i])
    {
        for(int j=i;j<=n;j += i)
        {
            if(!phi[j])  phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }