Bạn là tay trống của ban nhạc rock Denise and the Integers. Chiếc trống là một hình trụ được quấn quanh bởi một lưới ô chữ nhật.

Ban nhạc sắp biểu diễn ở Mathland. Khán giả Mathland rất khó tính và đòi hỏi mỗi ô trên trống chứa một số nguyên dương; không được dùng số 0 hay số âm. Hơn nữa, mỗi số nguyên \(K\) phải kề cạnh (chung một cạnh, không chỉ chung một điểm) với đúng \(K\) ô khác cũng chứa số \(K\): ô chứa 1 phải chạm đúng một ô khác chứa 1, ô chứa 2 phải chạm đúng hai ô khác chứa 2, v.v. Ngoài điều kiện đó, một ô chạm các ô mang giá trị khác như thế nào không quan trọng.

Hai mặt tròn trên và dưới của trống không được tính là ô và không cần trang trí. Vì vậy, mỗi ô ở hàng trên cùng và dưới cùng chỉ chạm ba ô khác, còn tất cả ô ở giữa chạm bốn ô.

Ví dụ, đây là một cách trang trí hợp lệ cho hình trụ tạo bởi lưới 3 hàng, 5 cột:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_ff258d7f.png

(Hãy hình dung hai cột khuất ở mặt sau của trống giống với ba cột đang nhìn thấy.)

Bạn muốn biết có bao nhiêu cách trang trí hợp lệ khác nhau. Hai cách trang trí là khác nhau nếu không thể xoay một cách quanh trục đối xứng của hình trụ để tạo ra cách kia. Mặt trên và mặt dưới của trống được coi là khác nhau, nên cách trang trí lưới \(3\times5\) dưới đây khác với cách phía trên:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_c4cf1ac1.png

(Một lần nữa, hãy hình dung hai cột khuất ở mặt sau giống với ba cột đang nhìn thấy.)

Trống có \(R\) hàng và \(C\) cột. Có bao nhiêu cách trang trí hợp lệ khác nhau? Kết quả có thể rất lớn, hãy trả về số cách modulo \(10^9+7\) (1000000007).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test là một dòng chứa hai số nguyên \(R\) và \(C\), lần lượt là số hàng và số cột của trống.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số cách trang trí hợp lệ modulo \(10^9+7\).

Ràng buộc

• Các ô chỉ được chứa số nguyên dương và phải thỏa điều kiện kề cạnh đã nêu.

Phân nhóm

• Test Set 1 (Nhỏ): \(1 \le T \le 20\), \(2 \le R \le 6\), \(3 \le C \le 6\).
• Test Set 2 (Lớn): \(1 \le T \le 100\), \(2 \le R \le 100\), \(3 \le C \le 100\).

Đ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ụ

2
2 4
3 5

    ???+ success "Output"

        ```sample
Case #1: 1
Case #2: 2

??? "Giải thích"

    Trong Case #1, lời giải duy nhất là điền số 3 vào tất cả các ô.

    Trong Case #2, hai lời giải duy nhất chính là hai cách được minh họa trong đề bài.

Nguồn

Google Code Jam 2015, Vòng 2, bài Drum Decorator.

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