Knight Moves 2

A knight stands on the top-left square of a $2n \times 2n$ chessboard. In one move the knight goes two squares in one direction and one square in the perpendicular direction, so its row and column change by $(\pm 1, \pm 2)$ or $(\pm 2, \pm 1)$. A move that leaves the board is not allowed.

The corner squares are the four squares at the corners of the board: top-left, top-right, bottom-left, and bottom-right.

Count the ways to make at most $k$ moves and finish on a corner square. Two ways are different if they use a different number of moves, or if they visit a different sequence of squares. The knight already stands on the top-left corner at the start, so making no move at all counts as one way.

Stated another way, for every $t$ with $0 \le t \le k$, count the paths that start on the top-left square, make exactly $t$ moves, and end on a corner square, then add all of those counts. A path may revisit a square, and it may enter a corner square and leave it again.

The first line contains the number of test cases $T$ ($1 \le T \le 50$).

Each of the next $T$ lines contains one test case: two integers $n$ and $k$ separated by a space ($2 \le n \le 24$, $1 \le k \le 10^9$).

For each test case, print the number of ways modulo $1000007$ on its own line.