ll inv(ll x,ll mod){
    if(x==1) return 1;
    return (mod-mod/x)*inv(mod%x,mod)%mod;
}