“Mùa hè cuối cùng cũng đã đến: đã tới lúc nghỉ ngơi, vui chơi, ra ngoài và tận hưởng thời tiết đẹp!” Alice nói. Cô là một kiểm lâm tận tụy làm việc tại một Vườn quốc gia nổi tiếng. Vào mùa hè, nhiều gia đình tới đây cắm trại, và nhiệm vụ của Alice là bố trí chỗ cho họ.

Alice phụ trách một khu cắm trại dạng ma trận \(N\times N\); mỗi ô có chỗ cho nhiều nhất một lều. Khi sắp xếp các gia đình, cô phải tuân thủ các quy định sau:

• Chỉ các gia đình có 1, 2 hoặc 3 thành viên được vào khu cắm trại. Mỗi lều chỉ chứa người của một gia đình, và một gia đình không thể bị chia ra nhiều lều.
• Vì lý do an ninh, Alice không muốn hàng hoặc cột nào quá đông hay quá vắng: mỗi hàng và mỗi cột phải có đúng 3 người.
• Theo chính sách an toàn của vườn, mỗi hàng và mỗi cột không được có quá 2 lều.

Alice còn biết trước rằng ít nhất \(X\) gia đình ba người sẽ tới, và sẽ luôn có đủ gia đình một hoặc hai người để lấp đầy phần còn lại.

Ví dụ, các cách bố trí sau hợp lệ với \(N=3\) và \(X=0\):

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

Các cách sau không hợp lệ với \(N=3\) và \(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

• Cách thứ nhất không hợp lệ vì phải có ít nhất một gia đình ba người.
• Ở cách thứ hai, hàng thứ ba (và cột thứ ba) không có đúng ba người.
• Ở cách thứ ba, cột thứ hai có hơn ba người (còn hàng thứ hai có ít hơn ba người).
• Cách cuối có hơn hai lều trong một hàng hoặc cột.

Alice muốn biết có bao nhiêu cách bố trí khác nhau với \(N\) và \(X\) đã cho. Hai cách bố trí \(A\) và \(B\) khác nhau nếu có một ô chứa lều trong cách này nhưng không chứa lều trong cách kia; hoặc nếu cùng ô đó đều có lều nhưng số thành viên trong lều ở \(A\) khác ở \(B\).

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm \(N,X\).

Dữ liệu ra

In Case #X: Y, với \(Y\) là số cách modulo \(10^9+7\).

Ràng buộc

• \(1\le T\le200\), \(0\le X\le N\).

Phân nhóm

• Nhỏ: \(1\le N\le20\).
• Lớn: \(1\le N\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 2
3 1
15 0

Case #1: 2
Case #2: 24
Case #3: 738721209

0 3  |  3 0
3 0  |  0 3

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Campinatorics.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.