## Derangements

Time Limit: 1 sec
Memory Limit: 64 MB
Attempts: 2
Accuracy: 0.00%
Author: Akashdeep Goel

There are N people who live in N different houses, such that P1 lives in house H1, P2 lives in H2 and so on. You know which house belongs to whom. Your task is to send every person into a different house such that P1 does not go to house H1, P2 does not go to house H2.... and person Pk does not go to house Hk. Given N and k, how many such different arrangements are possible. If no such arrangement is possible, output 0.

Input

The first line contains T, the number of test cases.

Each test case contains a single line, having two space separated integers- N and K. N is the total number of people, and k is the index such that no person from P1 to Pk goes to his own house.

Output

Output one integer per line, which contains the number of arrangements possible for that test case, modulo 1000000007.

Constraints

1<=T<=10

1<=N<=10^5

0<=K<=N

Example

Input

3

2 0

3 3

9962 491

Output

2

2

989784389

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

4 years ago

cpp

0.00 sec

0 KB

4 years ago

cpp14

0.00 sec

0 KB

5 years ago

cpp

0.07 sec

64 KB