- Prepare
- Mathematics
- Combinatorics
- Circles Math

# Circles Math

# Circles Math

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