Problem

You are the drummer in the rock band Denise and the Integers. Your drum is a cylinder around which you've wrapped a rectangular grid of cells.

Your band is scheduled to perform in Mathland. The Mathlanders are a tough audience, and they will expect every cell of your drum to contain a positive integer; zeroes and negative integers are not allowed. Moreover, each integer K must border (share an edge, and not just a point, with) exactly K other cells with the same integer -- that is, a cell with a 1 must touch exactly one other cell with a 1, a cell with a 2 must touch exactly 2 other cells with a 2, and so on. Apart from this restriction, it does not matter what other cells a cell touches. (The circular top and bottom of the drum do not count as cells and do not need to be decorated. Note that this means that the cells along the top and bottom of the drum only touch three other cells each, whereas all the other cells touch four other cells each.)

For example, this is a valid decoration of a cylinder formed by a grid with 3 rows and 5 columns:

(Again, imagine that the unseen two columns on the back of the drum are the same as the three visible columns.)

Your drum has R rows and C columns. How many different valid decorations are possible? The number may be large, so return the number of decorations modulo 10⁹ + 7 (1000000007).

Input

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of valid decorations modulo 10⁹ + 7, as described above.

Limits

Memory limit: 1 GB.

Small dataset (11 Points)

Time limit: 240 10 seconds.

1 ≤ T ≤ 20.

2 ≤ R ≤ 6.

3 ≤ C ≤ 6.

Large dataset (19 Points)

Time limit: 480 20 seconds.

1 ≤ T ≤ 100.

2 ≤ R ≤ 100.

3 ≤ C ≤ 100.

Sample

2
2 4
3 5

Case #1: 1
Case #2: 2

In Case #1, the only solution is to fill all cells with 3s.

In Case #2, the only two solutions are the two depicted in the problem statement.