Number Theory

namespace math
{
    ll qpow(ll x,ll y,ll m)
    {
        ll res=1;
        for(;y;y>>=1,x=x*x%m)
            if(y&1)res=res*x%m;
        return res;
    }

    ll qpow(ll x,ll y,ll m)
    {
        ll res=1;
        for(x=x<m?x:x%m+m;y;y>>=1)
        {
            if(y&1)
            {
                res=res*x;
                res=res<m?res:res%m+m;
            }
            x=x*x;
            x=x<m?x:x%m+m;
        }
        return res;
    }
}

namespace math
{
    const int __=1e6+5;

    bool pri[__];
    int num[__],to[__];

    void prime()
    {
        pri[0]=pri[1]=true;
        for(int i=2;i<__;++i)
        {
            if(!pri[i])
            {
                num[++num[0]]=i;
                to[i]=i;
            }
            for(int j=1;j<=num[0] && i*num[j]<__;++j)
            {
                int p=i*num[j];
                pri[p]=true;
                to[p]=num[j];
                if(!(i%num[j]))break;
            }
        }
    }
}

namespace math
{
    ll pri_div[16];
    void div(ll x)
    {
        int y=(int)sqrt(x+0.1);
        for(int i=2;i<=y;i++)
            if(x%i==0)
                for(pri_div[++pri_div[0]]=i;x%i==0;x/=i);
        if(x!=1)pri_div[++pri_div[0]]=x;
    }
}

namespace math
{
    ll phi(ll x)
    {
        ll y=x,p=x;
        for(ll i=2;i*i<=x;i++)
            if(y%i==0)for(p-=p/i;y%i==0;y/=i);
        if(y!=1)p-=p/y;
        return p;
    }
}

namespace math
{
    const int __=1e6+5;
    int phi[__],num[__];
    void euler()
    {
        phi[1]=1;
        for(int i=2;i<__;i++)
        {
            if(!phi[i])
            {
                num[++num[0]]=i;
                phi[i]=i-1;
            }
            for(int j=1;j<=num[0] && i*num[j]<__;++j)
            {
                int &p=num[j];
                if(!(i%p))
                {
                    phi[i*p]=phi[i]*p;
                    break;
                }
                else phi[i*p]=phi[i]*(p-1);
            }
        }
    }
}

namespace math
{
    struct eg{ll x,y,r;eg(ll x,ll y,ll r):x(x),y(y),r(r){}};
    eg exgcd(ll a,ll b)
    {
        if(!b)return eg(1,0,a);
        eg t=exgcd(b,a%b);
        return eg(t.y,t.x-a/b*t.y,t.r);
    }
}

namespace math
{
    ll lce(ll r[],ll m[],int n)
    {
        for(int i=2;i<=n;i++)
        {
            eg t=exgcd(m[1],m[i]);
            if((r[i]-r[1])%t.r)return -1;
            ll md=m[i]/t.r;
            t.x=((r[i]-r[1])/t.r*t.x%md+md)%md;
            r[1]+=m[1]*t.x,m[1]=m[1]/t.r*m[i];
        }
        return r[1];
    }
}

namespace math
{
    int pri_root(ll x)
    {
        div(x-1);
        for(int i=2;i<=x-1;i++)
        {
            bool flag=true;
            for(int j=1;j<=pri_div[0] && flag;j++)
                if(qpow(i,(x-1)/pri_div[j],x)==1)
                    flag=false;
            if(flag)return i;
        }
    }
}

namespace math
{
    const int __=5e6;

    bool pri[__+5];
    int mu[__+5],num[__+5];

    void mobius()
    {
        mu[1]=1,pri[1]=true;
        for(int i=2;i<=__;i++)
        {
            if(!pri[i])
            {
                num[++num[0]]=i;
                mu[i]=-1;
            }
            for(int j=1;j<=num[0] && i*num[j]<=__;++j)
            {
                int &p=num[j];
                pri[i*p]=true;
                if(!(i%p)){mu[i*p]=0;break;}
                mu[i*p]=-mu[i];
            }
        }
    }
}

template<int p>//p是<=1e6的质数
struct combination
{
    int fac[p],inv[p];
    combination()
    {
        fac[0]=1,inv[0]=1;
        for(int i=1;i<p;i++)
        {
            fac[i]=1ll*fac[i-1]*i%p;
            inv[i]=qpow(fac[i],p-2);
        }
    }

    int c(int n,int k)
    {
        if(k>n)return 0;
        return 1ll*fac[n]*inv[k]%p*inv[n-k]%p;
    }

    int lucas(ll n,ll k)
    {
        if(!k)return 1;
        return 1ll*c(n%p,k%p)*lucas(n/p,k/p)%p;
    }

    int qpow(int x,int y)
    {
        int res=1;
        for(;y;y>>=1,x=1ll*x*x%p)
            if(y&1)res=1ll*res*x%p;
        return res;
    }
};