Adjacent Rooks

Time limit1sMemory limit512 MB

Summary

Count permutations of n rooks on an n x n board with no shared row or column that have exactly k diagonally adjacent pairs, modulo 1e9+7.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

Professor Oak is preparing a problem for his students. The problem consists in counting the number of ways of placing $n$ rooks on an $n \times n$ chessboard such that no rook is threatening another rook (that is, no two rooks are in the same column or in the same row).

However, this problem is too easy, so he has decided to add a twist. He only wants you to count the number of solutions in which there are exactly $k$ pairs of rooks that are diagonally adjacent (that is, they are in neighboring columns and in neighboring rows). Can you solve it?

Output your answer modulo $10^9 + 7$ .

Input

The first line contains a single integer $t$ , the number of test cases ( $1 \leq t \leq 5000$ ).

Each test case is given on a single line containing two integers $n$ and $k$ : ( $1 \leq n \leq 1000$ ; $0 \leq k \leq n-1$ ): the number of rooks and the number of pairs of rooks that must be diagonally adjacent.

Output

Print one integer: the number of ways to place $n$ rooks such that no two are in the same row or column and such that there are exactly $k$ pairs of diagonally adjacent rooks. The answer must be expressed modulo $10^9 + 7$ .

Examples1

Example 1
Input
```
5
1 0
2 0
3 1
3 2
4 2
```
Expected output
```
1
0
4
2
10
```