Campground Arrangements (Large)

Alice is a ranger who runs one of the camps in a national park. The camp is an $N \times N$ grid, and each cell holds at most one tent. When Alice places families in the camp she has to follow these rules.

• Only families of 1, 2 or 3 members are allowed in the camp. A tent holds members of a single family, and a family cannot be split across several tents.
• For safety, the number of people in each row and in each column is exactly 3.
• Under the park's safety policy, no row and no column holds more than 2 tents.

Alice knows in advance that at least $X$ three-member families will visit. There are enough one-member and two-member families to fill the rest of the camp.

Write in each cell the number of people in the tent placed there, and write 0 in a cell with no tent. For example, both of these arrangements follow every rule for $N = 3$ and $X = 0$.

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

These four arrangements break a rule for $N = 3$ and $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

• The first one has no three-member family.
• The second one has a third row and a third column whose people do not add up to 3.
• The third one has more than 3 people in the second column and fewer than 3 in the second row.
• The fourth one places more than 2 tents in a row and in a column.

Two arrangements $A$ and $B$ are different if a cell holds a tent in one of them and is empty in the other, or if the same cell holds tents with a different number of members. Given $N$ and $X$, count the different arrangements.

The first line contains $T$, the number of test cases. Each of the next $T$ lines holds one test case: two integers $N$ and $X$, the number of rows and columns of the camp and the minimum number of three-member families.

Limits

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

For each test case, print one line in the form Case #i: A, where $i$ is the test case number starting from 1 and $A$ is the number of possible arrangements. The answer can be huge, so print it modulo $10^9 + 7$.

For $N = 2$ and $X = 2$ only these two arrangements follow the rules.

0 3  |  3 0
3 0  |  0 3