题意：长度为n的序列,前m位恰好k位正确排序，求方法数
前m位选k个数正确排,为cm[m][k],剩余m - k个空位，要错排，这m - k个数可能是前m个数中剩下的，也可能来自后面的n - m个数
考虑这样一个问题,共n个数，前i位错排的方法数，显然dp[i][0] = i!
递推考虑：处理到第i个数时，等价于前i - 1个数错排的方法数减去在前i - 1个数错排的情况下第i位恰好为i的方法数，后者相当于n - 1个数前i - 1位错排
所以 dp[n][i] = dp[n][i - 1] - dp[n - 1][i - 1]
故结果为：
cm[m][k] * dp[n - k][m - k]
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 1008, INF = 0x3F3F3F3F;
const LL MOD = 1000000007; LL cm[N][N], dp[N][N]; void init(){
memset(cm, 0, sizeof(cm));
cm[0][0] = 1; for(int i = 1; i < N; i++){
cm[i][0] = 1;
for(int j = 1; j <= i; j++){
cm[i][j] = (cm[i - 1][j - 1] + cm[i - 1][j]) % MOD;
}
}
dp[0][0] = 1;
for(int i = 1; i < N; i++){
dp[i][0] = (dp[i - 1][0] * i) % MOD;
} for(int i = 1; i < N; i++){
for(int j = 1; j <= i; j++){
dp[i][j] = ((dp[i][j - 1] - dp[i - 1][j - 1] ) % MOD + MOD) % MOD;
}
} } int main(){
init();
int t;
cin >> t;
for(int i = 1; i <= t; i++){
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
printf("Case %d: %lld\n", i, cm[m][k] * dp[n - k][m - k] % MOD); }
return 0;
}