SP5975 TRKNIGHT - Travelling Knight
题目描述
你需要完成一个简单的任务：在一个 $2n$ 行 $2n$ 列的棋盘上，一名骑士从左上角开始移动。要求计算出骑士在最多移动 $K$ 步后，到达棋盘任意一个角落的方法数。
输入格式
第一行是整数 $T$，表示测试用例的数量。接下来 $T$ 行，每行包含两个整数 $n$ 和 $k$。
输出格式
对应每个测试用例，输出移动结束后骑士能到达角落的方案数，结果对 $1000007$ 取模。
**样例**
#### 输入
```
3
2 1
2 2
3 3
```
#### 输出
```
1
5
7
```
说明/提示
- $1 \le T \le 20$
- $2 \le n \le 12$
- $1 \le k \le 1000000000$
这道题要求在指定步骤内，以尽可能少的计算实现方案数目，并确保计算结果不会超出较大的数字范围。要注意，骑士只能在确定的步数范围内移到棋盘的角落。
**本翻译由 AI 自动生成**