Wand FZU

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).

Sample Input

2
1 1
3 1

Sample Output

1
4

现在一群 wizard 在开会，进入会议室的时候，每个人将自己的 wand 放到了桌子上，现在开会结束了，
在 wizard 们将要离开的时候，将 wand 原来的摆放顺序打乱，那 wizard 将桌子上的 wang 拿走时： 
要求：至少有 K 个人拿到的是自己原来的 wand 。问，有多少种打乱顺序的方法
首先在 n 个中拿出 k 到 n 个，是放在原来的位置，方法有 C(n,i)种，然后将剩下的那些 wand 错排
 
预处理阶乘逆元

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <iostream>
 8 #include <map>
 9 #include <stack>
10 #include <string>
11 #include <vector>
12 #define  pi acos(-1.0)
13 #define  eps 1e-6
14 #define  fi first
15 #define  se second
16 #define  lson l,m,rt<<1
17 #define  rson m+1,r,rt<<1|1
18 #define  bug         printf("******
")
19 #define  mem(a,b)    memset(a,b,sizeof(a))
20 #define  fuck(x)     cout<<"["<<x<<"]"<<endl
21 #define  f(a)        a*a
22 #define  sf(n)       scanf("%d", &n)
23 #define  sff(a,b)    scanf("%d %d", &a, &b)
24 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
25 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
26 #define  pf          printf
27 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
28 #define  FREE(i,a,b) for(i = a; i >= b; i--)
29 #define  FRL(i,a,b)  for(i = a; i < b; i++)
30 #define  FRLL(i,a,b) for(i = a; i > b; i--)
31 #define  FIN         freopen("DATA.txt","r",stdin)
32 #define  gcd(a,b)    __gcd(a,b)
33 #define  lowbit(x)   x&-x
34 #pragma  comment (linker,"/STACK:102400000,102400000")
35 using namespace std;
36 typedef long long  LL;
37 const int INF = 0x7fffffff;
38 const int mod = 1e9 + 7;
39 const int maxn = 1e5 + 10;
40 int n, k, t;
41 LL ans[maxn], a = 0, b = 1;
42 void init() {
43     ans[1] = a, ans[2] = b;
44     for (int i = 3 ; i <= 10010 ; i++) {
45         ans[i] = (((i - 1) % mod) * ((a + b) % mod)) % mod;
46         a = b;
47         b = ans[i];
48     }
49 }
50 LL C(int k, int n) {
51     LL ret = 1;
52     for (int i = n - k + 1; i <= n; i++)  ret *= i;
53     for (int i = 2; i <= k; i++)  ret /= i;
54     return ret;
55 }
56 LL c[20000010];
57 
58 long long modexp(long long a, long long b, int mod) {
59     long long res = 1;
60     while(b > 0) {
61         if (b & 1) res = res * a % mod;
62         b = b >> 1;
63         a = a * a % mod;
64     }
65     return res;
66 }
67 
68 void cal() {
69     LL ans = 1;
70     for(int i = 1; i <= 1e7; i ++) {
71         ans *= i;
72         ans %= mod;
73         c[i] = ans;
74     }
75 }
76 int main() {
77     cal();
78     c[0] = 1;
79     init();
80     sf(t);
81     while(t--) {
82         sff(n, k);
83         LL ret = 1;
84         for (int i = k ; i <= n ; i++) {
85             LL fz = c[n];
86             LL fm = (c[i] * c[n - i]) % mod;
87             LL a1 = (fz * (modexp(fm, mod - 2, mod) % mod)) % mod;
88             ret = (ret + a1 * ans[n - i] % mod) % mod;
89         }
90         printf("%lld
", ret % mod);
91     }
92     return 0;
93 }