Given an $n*n$ chessboard where you want to place some chess kings and $k$ chess rooks. You have to find the number of ways that no two rooks attack each other, no two kings attack each other, no rooks attack kings. (But kings can attack rooks.)

Because the result may be very large, please print the result modulo $1000000007$.

P.S. Two rooks attack each other if and only if thay are on the same rows or same columns.
Two kings attack each other if and only if one is on the other's adjacent 8 cells (vertical, horizontal or diagonal).
A rook attack a king if and only if the king is on the same rows or the same columns as the rook.

The first line contains an integer $T$(about 10),indicating the number of cases.
Each test case begins with two integers $n(1 \leq n \leq 15)$ and $k(0 \leq k \leq 15)$.

For each case, output an integer means the answer mod $1000000007$.

5
1 0
1 1
2 0
2 1
2 2

2
1
5
8
2

BestCoder Round #31