Consider this sequence {1, 2, 3 ... N}, as an initial sequence of first N natural numbers. You can rearrange this sequence in many ways. There will be a total of N! arrangements. You have to calculate the number of arrangement of first N natural numbers, where in first M positions; exactly K numbers are in their initial position.

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

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

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

Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case contains three integers N (1 ≤ N ≤ 1000), M (M ≤ N), K (0 < K ≤ M).

Output
For each case, print the case number and the total number of possible arrangements modulo 1000000007.

Sample Input
2

5 3 2

10 6 3

Sample Output
Case 1: 12

Case 2: 64320

前m里k个数字在原位置为C(m,k),剩下的m-k个位置，利用容斥原理来做。减去有1个在原位置的方案，加上2个在原位置的方案，再减去3个在原位置的方案……即减去单数的加上偶数的在原位置的方案。

[latex]ans = C\binom{k}{m} * ∑ (C\binom{i}{n-k} * A\binom{n-k-i}{n-k-i} * (-1)^i ) \mod mod[/latex]

• 由于容斥原理求的是[latex] \mid \cup A_i \mid [/latex] 而这题求的是[latex] \mid \cap A_i \mid [/latex] 所以需要变化一下。
• 某班54人，共三项活动，参加一项的分别有25，22，34人，参加两项的12，18，14人，求三项都参加的人数。可以猜到这题最后用54减去容斥结果。
• 推广而来就是由全集减去容斥结果。
• 具体证明：容斥原理

• 由于c++里面%的结果的符号取决于被mod的数，所以会有负数结果。例如：
• [latex]{(4-2)\mod 3=4\ mod 3-2\mod 3=(1-2)\mod 3=-1\mod 3=-1}[/latex]
• 所以当结果小于0的时候要加上mod的数字。

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
ll po[1010]={0};
ll se[1010][1010];
ll mo=1000000007;
ll t,n,m,k;
ll c(ll mm,ll nn)
{
	//if(nn==0) return 1;
	//return po[mm]/(po[nn]*po[mm-nn])%mo;
	return se[mm][nn];
}
int main()
{
	po[0]=1;
	for(int i=1;i<=1000;i++)
	{
		po[i]=po[i-1]*i%mo;
		se[i][0]=1;
	}
	se[0][0]=1;
	for(int i=1;i<=1000;i++) 
		for(int j=1;j<=i+1;j++)
			se[i][j]=(se[i-1][j-1]+se[i-1][j])%mo;
	scanf("%lld",&t);
	for(ll i=1;i<=t;i++)
	{
		ll ans=0,res=0;
		scanf("%lld%lld%lld",&n,&m,&k);
		for(ll j=0;j<=m-k;j++)
		{
			ll temp=c(m-k,j)*po[n-k-j];
			if(~j&1) res+=temp;
			else res-=temp;
			//if(res<0) res+=mo; 
			res=res%mo;
			if(res<0) res+=mo;
		}
		ans=res*c(m,k)%mo;
		printf("Case %lld: %lld\n",i,ans);
	}
	
}