Knight Moves to a Corner

A knight stands on the top left square of a $2n \times 2n$ chessboard. In one move the knight goes 1 square in one direction and 2 squares in the perpendicular direction, and it may not leave the board. It may step on a square it has already visited.

Count the ways to move the knight at least $0$ and at most $k$ times so that it ends on one of the four corner squares of the board. Two ways are different if the number of moves differs, or if the sequence of visited squares differs anywhere. The starting square is already a corner, so making no move at all counts as one way.

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

Each of the next $T$ lines holds one test case with $n$ and $k$ separated by a space ($2 \le n \le 12$, $1 \le k \le 10^9$).

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