在n×nn\times nn×n的棋盘上，有多少种方式放 nnn 个棋子，使得没有两个棋子在同一列，没有两个棋子在同一行，且有kkk对棋子满足其曼哈顿距离为 222 ，答案模109+710^9+7109+7输出。
曼哈顿距离，即 111-范数，按如下方法计算：设 (x1,y1)(x_1,y_1)(x1,y1) 和 (x2,y2)(x_2,y_2)(x2,y2) 是平面上的两点，则这两点间的曼哈顿距离为 ∣x1−x2∣+∣y1−y2∣\left|x_1-x_2\right|+\left|y_1-y_2\right|∣x1−x2∣+∣y1−y2∣。
第一行一个正整数 T (1≤T≤1000)T\ (1\leq T \leq 1000)T (1≤T≤1000)，表示数据组数。
接下来 TTT 行，每行两个整数 n,k (1≤n≤1000,0≤k≤n)n,k\ (1\leq n\leq 1000,0\leq k\leq n)n,k (1≤n≤1000,0≤k≤n)。
输出 TTT 行，每行一个非负整数表示答案。
5 1 0 2 0 3 1 3 2 4 2
1 0 4 2 10