Consider this sequence {1, 2, 3, … , N}, as a initial sequence of firstN natural numbers. You can rearrange this sequence in many ways. Therewill beN! different arrangements. You have to calculate the number ofarrangement of firstN natural numbers, where in first M (M<=N)positions, exactlyK (K<=M) numbers are in its initial position.

Example:

For, N = 5, M = 3, K =2

You should count this arrangement {1, 4, 3, 2, 5}, here in first 3positions 1 is in 1^st position and 3 in 3^rd position. Soexactly 2 of its first 3 are in there initial position.

But you should not count this {1, 2, 3, 4, 5}.

Input

The first line ofinput is an integer T(T<=1000) that indicates the number of testcases. Next T line contains 3 integers each,N(1<=N<=1000), M,and K.

Output

For each case,output the case number, followed by the answer modulo 1000000007. Lookat the sample for clarification.

SampleInput                             Outputfor Sample Input

Special Thanks : Abdullah Al Mahmud, Jane Alam Jan

题意：可以把序列1-n任意重排，但重排后的前m个位置中恰好要有k个是不变的，输入整数n，m，k，输出重排数%1000000007.

思路：首先从前m个选出k作为不变的，然后剩下的n-k个再任意重排，也是从中选出i个来作为不变的，剩下的错排。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1005;
const ll mod = 1000000007;

ll dp[maxn], C[maxn][maxn];
int n, m, k;

void init() {
	memset(C, 0, sizeof(C));
	C[0][0] = 1;
	for (int i = 1; i < maxn; i++) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; j++)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
	}

	dp[1] = 0, dp[0] = dp[2] = 1;
	for (int i = 3; i < maxn; i++)
		dp[i] = ((i - 1) * (dp[i-2] + dp[i-1]) % mod) %  mod;
}

ll solve() {
	ll ans = 0;
	int t = n - m;
	for (int i = 0; i <= t; i++) 
		ans = (ans + C[t][i] * dp[n-k-i]) % mod;
	return (ans * C[m][k]) % mod;
}

int main() {
	init();
	int cas = 1;
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &k);
		printf("Case %d: %lld\n", cas++, solve());	
	}
	return 0;
}

UVA - 11481 Arrange the Numbers