提示: 欢迎访问OurACM平台。
Problem 2040 Tiling

Accept: 127    Submit: 288
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

We can perfectly tile one m*n rectangle by any size of tiles. The following picture shows all the 34 possible ways to perfectly title a 3*2 rectangle.
Now you are given one m*n rectangle, your task is to calculate the total number of the ways to perfectly title the given rectangle. Please mod the answer with 1,000,000,007 when you output it.

Input

The first line of the input contains an integer T(T≤100), indicating the number of test cases. Following is T lines, each containing two integer numbers m(1≤m≤6) and n(1≤n≤1,000,000,000).

Output

For each test case, print a line containing the test case number (beginning with 1) and the answer.

Sample Input

2 2 2 3 2

Sample Output

Case 1: 8 Case 2: 34

Source

2011年全国大学生程序设计邀请赛(福州)

Submit  Back  Status  Discuss