ll inv[maxn];
inv[1] = 1;
rep(i,2,maxn) 
    inv[i] = inv[mod%i] * (mod-mod/i) % mod;

ll f[maxn];
ll f[1] = 1;
rep(i,2,maxn)
    f[i] = f[i-1]*i;

ll cur,p[maxn],q[maxn],inv[maxn];
ll C(ll n,ll k){
    return p[n]*q[k]%mod*q[n-k]%mod;
}
ll c(ll n,ll k){
    if(n<maxn) return C(n,k);
    if(!k) return 1;
    return cur = cur*inv[k]%mod*((n-k+1)%mod)%mod;
}
void init(){
    p[0]=p[1]=q[0]=q[1]=inv[0]=inv[1]=1;
    for(ll i = 2;i<maxn;i++){
        inv[i] = (mod-mod/i)*inv[mod%i]%mod;
        q[i] = q[i-1] * inv[i] % mod;
        p[i] = p[i-1] * i % mod;
    }
}
//在每次的时候就得cur初始化为1

int A(int n,int k){
    return c(n,k)*p[k]%mod;
}

int inv[maxn];
int inv[1] = 1;
rep(i,2,max){
    inv[i] = inv[mod%i]*(mod-mod/i)%mod;
}

ll extend_gcd(ll a,ll b,ll x,ll y){
    if(a==0 && b==0) return -1;
    if(b==0) {
        x = 1;y = 0;
        return a;
    }
    ll d = extend_gcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}
ll mod_reverse(ll a,ll n){
    ll x,y;
    ll d = extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}