캠핑장 배치 세기 (큰 입력)

앨리스는 국립공원의 캠핑장 한 곳을 관리하는 관리인이다. 캠핑장은 $N \times N$ 크기의 격자이고, 각 칸에는 텐트를 최대 한 개까지 칠 수 있다. 가족을 배치할 때 앨리스가 지켜야 하는 규칙은 다음과 같다.

• 구성원이 1명, 2명, 3명인 가족만 들어올 수 있다. 한 텐트에는 한 가족만 들어가고, 한 가족을 여러 텐트에 나누어 배치할 수 없다.
• 안전을 위해 각 행과 각 열의 인원 합은 정확히 3명이어야 한다.
• 공원 안전 수칙에 따라 각 행과 각 열에 놓인 텐트는 2개를 넘을 수 없다.

앨리스는 3인 가족이 최소 $X$팀 방문한다는 사실을 미리 알고 있다. 남은 자리를 채울 1인 가족과 2인 가족은 충분히 많다.

격자의 각 칸에 그 칸에 놓인 텐트의 인원 수를 적고, 텐트가 없는 칸에는 0을 적는다. 예를 들어 $N = 3$, $X = 0$일 때 다음 두 배치는 규칙을 모두 만족한다.

1  2  0  |  3  0  0
0  1  2  |  0  1  2
2  0  1  |  0  2  1

반면 $N = 3$, $X = 1$일 때 다음 네 배치는 규칙을 어긴다.

1  2  0  |  0  3  0  |  1  2  0  |  1  1  1
0  1  2  |  3  0  0  |  0  2  0  |  1  1  1
2  0  1  |  0  0  0  |  2  0  1  |  1  1  1

• 첫 번째 배치에는 3인 가족이 한 팀도 없다.
• 두 번째 배치는 셋째 행과 셋째 열의 인원 합이 3이 아니다.
• 세 번째 배치는 둘째 열의 인원 합이 3보다 크고, 둘째 행의 인원 합이 3보다 작다.
• 네 번째 배치는 한 행과 한 열에 텐트를 2개보다 많이 놓았다.

두 배치 $A$와 $B$는 한쪽에서 텐트가 놓인 칸이 다른 쪽에서는 비어 있거나, 같은 칸에 놓인 텐트의 인원 수가 서로 다르면 다른 배치로 센다. $N$과 $X$가 주어질 때 서로 다른 배치의 수를 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 캠핑장의 행과 열의 개수 $N$, 3인 가족의 최소 팀 수 $X$가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 200$
• $1 \le N \le 10^6$
• $0 \le X \le N$

각 테스트 케이스마다 한 줄에 Case #i: A 형식으로 답을 출력한다. $i$는 1부터 시작하는 테스트 케이스 번호이고, $A$는 가능한 배치의 수이다. 답이 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

$N = 2$, $X = 2$일 때 규칙을 만족하는 배치는 다음 두 가지뿐이다.

0 3  |  3 0
3 0  |  0 3