2013年7月9日 星期二

11481 - Arrange the Numbers


A
Arrange the Numbers


給定一個序列 {1, 2, 3, ..., N} 前 N 個自然數。有很多重新排列的方法,將會有 N!不同的排列方式,現在要計算在前 N 個自然數的排列中,前 M 個數字,恰好有 K 個數字在原本的位置上的方法數共有幾種。
(K <= M <= N)

例如:N = 5, M = 3, K =2

其中一種排列為  {1, 4, 3, 2, 5},在前三個位置中,位置 1 剛好是 1,且位置 3 剛好也是 3。因此恰好有兩個數字在前三個位置中的原本位置。

但是不會有 {1, 2, 3, 4, 5} 這種排列。

Input
第一行會有一個整數 T(T<=1000),表示接下來會有幾筆測資。
接下來有 T 行,每行上有三個整數  N(1<=N<=1000), M, K

Output
對於每組測資輸出 mod  1000000007 的結果

Sample Input                             Output for Sample Input

1
5 3 2

Case 1: 12


Problem Setter : Md. Arifuzzaman Arif
Special Thanks : Abdullah Al Mahmud, Jane Alam Jan