You are given a set A containing n integers from 1 to n; A = {1,2,3,...n}.

Let's call P(A) as a set that contains all permutations of A;

For eg: if A = {1,2}. P(A) = {{1,2},{2,1}}

Can you find the number of elements a ∈ P(A) which satisfies following conditions:

For every 1 <= i <= n, a[i] ≠ i where a[i] is the i^{th} integer in permutation a
There exists a set of k integers {i_{1}, i_{2}, i_{3}, .... i_{k}} such that
a[i_{j}] = i_{j+1} ∀ j < k and a[i_{k}] = i1 (cyclic)

Input Format

The first line contains an integer T indicating the number of test-cases.
T lines follow. Each line has two integers n and k separated by a single space.

Constraints

1 <= T <= 100

1 <= k <= n <= 10^{6}

Output Format

Output the remainder of the answer after divided by 1000000007 ie., (10^{9}+7)

Sample Input

4
3 2
4 2
5 3
6 2

Sample Output

0
3
20
105

Hint

10^{9}+7 is a prime number.

Explanation

note : Array's are 1 indexed.

Lets take a look at N = 3 and K = 2

We will get 2 sets of A that satisfy the first property a[i] ≠ i, they are

[3,1,2]
[2,3,1]

Now, as K = 2, we can have 6 such elements.

[1,2], [1,3],[2,3], [2,1], [3,1], [3,2]

Lets consider the first element of P(A) -> [3,1,2]

[1,2], a[1] ≠ 2
[1,3], a[1] = 3 but a[3] ≠ 1
[2,3], a[2] ≠ 3
[2,1], a[2] = 1 but a[1] ≠ 2
[3,1], a[3] = 1 but a[1] ≠ 3
[3,2], a[3] ≠ 2

Lets consider the second element of P(A) -> [2,3,1]

[1,2], a[1] = 2 but a[2] ≠ 1
[1,3], a[1] ≠ 3
[2,3], a[2] = 3 but a[3] ≠ 3
[2,1], a[2] ≠ 1
[3,1], a[3] = but a[1] ≠ 3
[3,2], a[3] ≠ 2

As none of the elements of a satisfy the properties above, hence 0.

In the second case, n=4,k=2. Here follows all the permutations of

A={1,2,3,4} we could find that satisfy the two condition above.

2 1 4 3 # (a[2] = 1, a[1] = 2) or (a[4] = 3, a[3] = 4) is ok.

4 3 2 1 # (a[4] = 1, a[1] = 4) or (a[3] = 2, a[2] = 3) is ok.

3 4 1 2 # (a[3] = 1, a[1] = 3) or (a[4] = 2, a[2] = 4) is ok.

Timelimits
Timelimits for this challenge is given here

见题面

见题面