나이트의 이동 2

크기가 $2n \times 2n$인 체스판의 가장 왼쪽 위 칸에 나이트가 하나 놓여 있다. 나이트는 한 번 움직일 때 한 방향으로 두 칸, 그와 수직인 방향으로 한 칸 이동한다. 즉 행과 열이 각각 $(\pm 1, \pm 2)$ 또는 $(\pm 2, \pm 1)$만큼 바뀐다. 체스판 밖으로 나가는 이동은 할 수 없다.

모서리 칸은 체스판의 네 꼭짓점에 있는 칸, 즉 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 칸이다.

나이트를 최대 $k$번 움직여서 모서리 칸에 도착하는 방법의 수를 구하는 프로그램을 작성하시오. 이동 횟수가 다르거나 지나는 칸의 순서가 다르면 서로 다른 방법으로 센다. 나이트는 처음부터 왼쪽 위 모서리에 있으므로 한 번도 움직이지 않는 것도 방법 하나로 센다.

정리하면 $0 \le t \le k$인 모든 $t$에 대해, 왼쪽 위 칸에서 출발해 정확히 $t$번 움직인 뒤 모서리 칸에서 끝나는 경로의 개수를 구하고, 그 값을 모두 더한다. 같은 칸을 여러 번 지나도 되고, 모서리 칸에 들어갔다가 다시 나와도 된다.

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

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

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