캠피네이터릭스

"드디어 여름이 왔어. 이제 쉬면서 즐거운 시간을 보내고, 밖에 나가 좋은 날씨를 만끽할 때야!"라고 유명한 국립공원에서 일하는 매우 헌신적인 관리인 Alice가 말한다. 여름에는 많은 가족이 휴가를 내어 그곳에서 야영하며 즐거운 시간을 보내고, 방문객들을 수용하는 것은 Alice의 일이다.

Alice는 공원 곳곳에 있는 여러 야영장 중 하나를 담당한다. 야영장은 크기가 N x N인 행렬로 나타낼 수 있으며, 각 칸에는 최대 하나의 텐트를 놓을 공간이 있다. 야영장에 가족들을 배치하려면 Alice는 다음과 같은 여러 규정을 따라야 한다:

• 구성원이 1, 2 또는 3명인 가족만 야영장에 들어올 수 있다. 또한 각 텐트에는 한 가족의 구성원만 머물 수 있으며, 한 가족이 여러 텐트로 나뉘어서는 안 된다.

• 보안상의 이유로 Alice는 행이나 열이 너무 붐비거나 너무 비어 있기를 원하지 않으므로, 각 행과 열에 정확히 3명의 구성원이 있기를 원한다.

• 또한 공원의 안전 정책에 따라 어떤 행이나 열에도 텐트가 2개보다 많아서는 안 된다.

그뿐만 아니라 Alice는 구성원이 세 명인 가족이 적어도 X가족 방문할 것이며, 야영장의 나머지를 채울 만큼 구성원이 한 명 또는 두 명인 가족이 충분히 있을 것임을 미리 알고 있다.

예를 들어, 다음은 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

• 첫 번째 배치는 구성원이 세 명인 가족이 적어도 한 가족 있어야 하므로 유효하지 않다.

• 두 번째 예는 세 번째 행(및 열)의 사람 수가 세 명이 아니므로 유효하지 않다.

• 세 번째 배치는 두 번째 열에 구성원이 세 명보다 많고 두 번째 행에는 세 명보다 적으므로 유효하지 않다.

• 마지막 예에는 행이나 열마다 텐트가 두 개보다 많이 있다.

마지막으로 Alice는 상황을 흥미롭게 유지하는 것을 좋아한다. 그녀는 N과 X가 주어졌을 때 서로 다른 배치가 몇 가지 가능한지 알고 싶다.

한 배치에는 텐트가 있는 칸에 다른 배치에는 텐트가 없거나, 두 배치의 같은 칸에 모두 텐트가 있지만 A에서 그 칸에 있는 구성원의 수와 B에서 같은 칸에 있는 구성원의 수가 다르면, 두 배치 A와 B는 서로 다른 것으로 간주한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 200. 0 ≤ X ≤ N.

작은 데이터 세트

시간 제한: 240초. 1 ≤ N ≤ 20.

큰 데이터 세트

시간 제한: 480초. 1 ≤ N ≤ $10^{6}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정확히 한 줄로 이루어지며, Alice의 야영장에 있는 행(및 열)의 수와 구성원이 세 명인 가족의 최소 수를 각각 나타내는 두 정수 N과 X가 주어진다.

각 테스트 케이스마다 "Case #X: Y"을 포함하는 한 줄을 출력한다. 여기서 X는 테스트 케이스 번호이며(1부터 시작한다), Y는 가능한 배치의 수이다.

답은 매우 클 수 있으므로, 답을 $10^{9}$ + 7로 나눈 나머지를 출력한다.

케이스 #1에는 서로 다른 유효한 배치가 두 가지 있다: