lucas定理求组合数+错排模板

int jc[M];
int f[M];int ksm(int a,int b){int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;
}
int c(int a,int b){return jc[a]%mod*ksm(jc[b]*jc[a-b]%mod,mod-2)%mod;
}
int lucas(int a,int b){if(!b)return 1;return (lucas(a/mod,b/mod)*c(a%mod,b%mod))%mod;
}
int n,m;
void solve(){cin>>n>>m;if(n==m){cout<<1<<endl;}else if(n-m==1){cout<<0<<endl;   }else if(m==0){cout<<f[n]<<endl;}else{int ans= (f[n-m]%mod*lucas(n,m))%mod;cout<<ans<<endl;}
}signed main()
{ios::sync_with_stdio(false),cin.tie(0);cout.tie(0);int T=1;cin>>T;f[1]=0;f[2]=1;jc[1]=1;jc[2]=2;for(int i=3;i<=1e6;i++){f[i]=((i-1)*(f[i-1]+f[i-2])%mod)%mod;jc[i]=jc[i-1]*i%mod;}while(T--){solve();}return 0;
}