Drum Decorator (Large)

You are the drummer in the rock band Denise and the Integers. Your drum is a cylinder, and a rectangular grid of cells is wrapped around its side.

Your band is booked to play in Mathland. The Mathlanders are a tough audience. They expect every cell of the drum to hold a positive integer, so zero and negative integers are not allowed. On top of that, each integer $K$ must border exactly $K$ other cells that hold the same integer $K$. Bordering means sharing an edge, and touching at a single point does not count. A cell holding 1 touches exactly one other cell holding 1, a cell holding 2 touches exactly two other cells holding 2, and so on. Apart from this rule, it does not matter what the other neighbours of a cell hold. The circular top and bottom of the drum are not cells and need no decoration, so a cell in the top row or in the bottom row touches only three other cells, while every other cell touches four.

For example, this is a valid decoration of a cylinder built from a grid with 3 rows and 5 columns.

Imagine that the two hidden columns on the back of the drum continue the three visible ones.

You want to know how many different valid decorations exist. Two decorations are different when no rotation around the axis of the cylinder turns one into the other. The top and the bottom of the drum are told apart, so the $3 \times 5$ decoration below differs from the one above.

Here too, the two hidden columns on the back continue the three visible ones.

Your drum has $R$ rows and $C$ columns. How many different valid decorations exist? The count can be large, so report it modulo $10^9 + 7$.

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

Limits

• $1 \le T \le 100$
• $2 \le R \le 100$
• $3 \le C \le 100$

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 $R = 2$ and $C = 4$, the only decoration fills every cell with 3.

For $R = 3$ and $C = 5$, there are exactly two decorations, and the two pictures in the statement show one each.