Description

相信大家入门算法的时候接触过八皇后问题。现在我们有一个 $n\times n$ 的棋盘，上面有 $n$ 个皇后，任意两个皇后不能在同一行或者同一列。但是皇后们可以跟斜相邻（这两个皇后的行数相邻，并且列数也相邻）的皇后进行交谈。给定 $K$，请计算有多少种放皇后的方式，满足恰好有 $K$ 对皇后可以交谈。

答案对 $10^{9}+7$ 取模。

Format

Input

第一行给定 $t$，表示数据组数。

第二行开始，每组数据给出两个整数 $n,K$。表示棋盘的宽度和皇后的个数和可以交谈的皇后对数。

Output

对于每组数据，给出一个整数表示放置方案数对 $10^{9}+7$ 取模的值。

Samples

5
1 0
2 0
3 1
3 2
4 2

1
0
4
2
10

Limitation

$1\mathrm{s},512\mathrm{MB}$

Subtasks

对于 $100\%$ 的数据满足，$1\leqslant t\leqslant 5000,1\leqslant n\leqslant 1000,0\leqslant k\leqslant n-1$。