Drum Decorator (Small)

You play drums in the rock band Denise and the Integers. Your drum is a cylinder, and its side is covered by a rectangular grid of cells.

The band is booked to play in Mathland. The audience there is demanding: every cell of the drum has to hold one positive integer, and zero or a negative integer is not allowed. On top of that, a cell holding $K$ must touch exactly $K$ other cells that hold $K$. Two cells touch when they share an edge, and cells that only meet at a corner do not count. A cell holding 1 touches exactly one other cell holding 1, and a cell holding 2 touches exactly two other cells holding 2. Apart from this rule, it does not matter what the remaining neighbours hold.

The circular top and bottom of the drum are not cells and are left undecorated, so a cell in the top row or the bottom row has three neighbours and every other cell has four. The side wraps all the way around the cylinder, so the first column and the last column touch each other as well.

For example, this is a valid decoration of a drum wrapped in a grid with 3 rows and 5 columns.

(Imagine that the two hidden columns on the back are the same as the three visible ones.)

You want to know how many valid decorations there are. Two decorations are different when no rotation about the axis of the cylinder turns one into the other. The top and the bottom of the drum are told apart, so the decoration below is different from the one above.

(Here too, the two hidden columns match the three visible ones.)

Your drum has $R$ rows and $C$ columns. How many different valid decorations are there? Report the count modulo $10^9+7$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $R$ and $C$ separated by a space, the number of rows and the number of columns of the drum.

Limits

• $1 \le T \le 20$
• $2 \le R \le 6$
• $3 \le C \le 6$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of valid decorations modulo $10^9+7$.

For a drum with $R=2$ and $C=4$, the only decoration writes 3 in every cell. For a drum with $R=3$ and $C=5$, the only decorations are the two shown above.