/*试除法判定质数*/
bool isprime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0) return false;
    return true;
}

/*试除法分解质因数*/
void divide(int x){
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            int s=0;
            while(x%i==0){
                x/=i;
                s++;
            }
            cout<<i<<" "<<s<<endl;
        }
    if(x>1) cout<<x<<" "<<1<<endl;
    cout<<endl;
}

/*朴素筛法求素数*/
int isprime[maxn],cnt;
bool st[maxn];// st[x]存储x是否被筛掉

void getprime(int n){
    for(int i=2;i<=n;i++){
        if(st[i]) continue;
        isprime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)
            st[j]=true;
    }
}

/*线性筛法求素数*/
int isprime[maxn],cnt;
bool st[maxn];// st[x]存储x是否被筛掉

void getprime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) isprime[cnt++]=i;
        for(int j=0;isprime[j]<=n/i;j++){
            st[isprime[j]*i]=true;
            if(i%isprime[j]==0) break;
        }
    }
}

/*试除法求所有约数*/
vector<int> getdivisor(int x){
    vector<int> res;
    for(int i=1;i<=x/i;i++)
        if(x%i==0){
            res.push_back(i);
            if(i!=x/i) res.push_back(x/i);
        }
    sort(res.begin(),res.end());
    return res;
}

/*欧几里得算法 最大公约数*/
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

/*求欧拉函数*/
int phi(int x){
    int res=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    if(x>1) res=res/x*(x-1);
    return res;
}

/*筛法求欧拉函数*/
int isprime[maxn],cnt;
int euler[maxn];// 存储每个数的欧拉函数
bool st[maxn];// st[x]存储x是否被筛掉

void geteuler(int n){
    euler[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            isprime[cnt++]=i;
            euler[i]=i-1;
        }
        for(int j=0;isprime[j]<=n/i;j++){
            int t=isprime[j]*i;
            st[t]=true;
            if(i%isprime[j]==0){
                euler[t]=euler[i]*isprime[j];
                break;
            }
            euler[t]=euler[i]*(isprime[j]-1);
        }
    }
}

/*快速幂*/
/*求m^k mod p,时间复杂度O(logk)*/
int qmi(int m,int k,int p){
    int res=1%p,t=m;
    while(k){
        if(k&1) res=res*t%p;
        t=t*t%p;
        k>>=1;
    }
    return res;
}

/*扩展欧几里得算法*/
/*求x y, s.t.ax+by=gcd(a,b)*/
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return d;
}

/*通过预处理逆元的方式求组合数*/
//首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
//如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a,int k,int p){//快速幂模板
    int res=1;
    while(k){
        if(k&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        k>>=1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0]=infact[0]=1;
for(int i=1;i<N;i++){
    fact[i]=(ll)fact[i-1]*i%mod;
    infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;
}