나이트의 이동

크기가 $2n \times 2n$인 체스판의 가장 왼쪽 위 칸에 나이트가 하나 놓여 있다. 나이트는 한 번 움직일 때 한 방향으로 1칸, 그와 수직인 방향으로 2칸 이동하며, 체스판 밖으로 나갈 수 없다. 이미 지나온 칸을 다시 밟아도 된다.

나이트를 $0$번 이상 $k$번 이하로 움직여서 마지막에 체스판의 네 꼭짓점 칸 중 하나에 있게 되는 이동 방법이 몇 가지인지 구하시오. 움직인 횟수가 다르거나 거쳐 간 칸의 순서가 한 곳이라도 다르면 서로 다른 방법으로 센다. 시작 칸이 이미 꼭짓점이므로 한 번도 움직이지 않는 방법도 한 가지로 센다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

다음 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 $n$과 $k$가 공백으로 구분되어 주어진다. ($2 \le n \le 12$, $1 \le k \le 10^9$)

각 테스트 케이스마다 방법의 수를 $1000007$로 나눈 나머지를 한 줄에 하나씩 출력하시오.