FZU 2282 Wand

• 2018-09-08
• 13
• 0

Description:

N wizards are attending a meeting. Everyone has his own magic wand. N magic wands was put in a line, numbered from 1 to n(Wand_i owned by wizard_i). After the meeting, n wizards will take a wand one by one in the order of 1 to n. A boring wizard decided to reorder the wands. He is wondering how many ways to reorder the wands so that at least k wizards can get his own wand.

For example, n=3. Initially, the wands are w1 w2 w3. After reordering, the wands become w2 w1 w3. So, wizard 1 will take w2, wizard 2 will take w1, wizard 3 will take w3, only wizard 3 get his own wand.

Input:

First line contains an integer T (1 ≤ T ≤ 10), represents there are T test cases.

For each test case: Two number n and k.

1<=n <=10000.1<=k<=100. k<=n.

Output:

For each test case, output the answer mod 1000000007(10^9 + 7).

2 1 1 3 1

Sample Output:

1 4

题目链接

n个数1~n求i\in [k,n]中i个数字在自己位置上的所有情况数量。

\sum_{i-k}^{n}C^{i}_{n}*Staggered[n-i]即为结果。

Staggered[0]要初始化为1,因为C^{i}_{n}*Staggered[0]为所有数都在自己位置上的数量，显然为1。