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.
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 one integer per line, which contains the number of arrangements possible for that test case, modulo 1000000007.