Professor Oak 正在为他的学生准备一道题目。题目要求计算在 $n \times n$ 的棋盘上放置 $n$ 个车的方法数，使得没有任何两个车互相攻击（即没有两个车在同一行或同一列）。

然而，这个问题太简单了，所以他决定增加一点难度。他只要求你计算满足以下条件的方案数：恰好有 $k$ 对车是“对角相邻”的（即它们位于相邻的列且位于相邻的行）。你能解决它吗？

请将答案对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 5000$)。

每个测试用例由一行给出，包含两个整数 $n$ 和 $k$ ($1 \le n \le 1000$; $0 \le k \le n-1$)：表示车的数量以及必须对角相邻的车对数。

输出格式

输出一个整数：在 $n \times n$ 的棋盘上放置 $n$ 个车，使得没有两个车在同一行或同一列，且恰好有 $k$ 对车对角相邻的方案数。答案必须对 $10^9 + 7$ 取模。

样例

样例输入 1

5
1 0
2 0
3 1
3 2
4 2

样例输出 1

1
0
4
2
10