求 1∼n 的排列 A 中，满足前 m 个数中，刚好有 K 个数使得 A[ i ]=i 的 AA 的个数。
错位排列
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define int long long
int c[1002][1002], F[1002] ;
void init(){
int i,j;
c[1][1]=1;
for(i=0;i<=1000;i++) c[i][0]=1;
for(i=2;i<=1000;i++)
for(j=1;j<=i;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j],c[i][j]%=mod;
F[0]=1;for(i=1;i<=1000;i++) F[i]=F[i-1]*i,F[i]%=mod;
}
int E(int n,int m){
int t= 0;
for(int i=0;i<=m;i++){
if(i%2==0)
t=(t+c[m][i]*F[n-i]%mod),t%=mod;
else
t=(t-c[m][i]*F[n-i]%mod+mod)%mod;
}
return t;
}
void sov(int cas){
int n,m,K;
cin>>n>>m>>K;
cout<<"Case "<<cas<<": "<<
c[m][K]*E(n-K,m-K)%mod<<endl;
}
signed main(){
init();
int tes;cin>>tes;
int cas=0;
while(tes--) sov(++cas);
}