Problem A
Abstract Painting
Gon is currently training to become a modern artist.
Everyday, Gon practices his painting skill on a rectangular canvas, divided into $R \cdot C$ unit squares, with $R$ rows and $C$ columns. Gon wants to paint all the edges of all unit squares.
Contrary to popular belief, creating a good modern painting is not an easy task. A good modern painting should use a limited number of colors, simple yet elegant. Thus, when creating his painting, Gon strictly adheres to the following rules:
-
Only $3$ colors are used: Red, Green and Blue.
-
All edges of all unit squares must be painted. Each edge must be painted with exactly one color.
-
For each unit square, exactly $2$ colors must be used to paint its $4$ edges. Furthermore, each color must be used to paint exactly $2$ edges.
In the following figure:
-
The painting on the left is a good painting.
-
The painting on the right is not a good painting, because the top-left unit square has $3$ blue edges.
Now Gon is wondering, how many different good paintings are there? Two paintings, both with $R$ rows and $C$ columns, are considered different, if there exists one edge painted with different colors in the two paintings. Please help Gon!
Input
The first line contains exactly one integer $T$ — the number of test cases $(1 \le T \le 5)$.
$T$ lines follow, each line contains exactly two integers $R$ and $C$ $(1 \le R \le 14, 1 \le C \le 2\, 000)$.
Output
Output exactly $T$ lines, each line contains a single integer — the number of different good paintings, modulo $10^{9} + 7$.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 1 1 2 2 1 |
18 108 108 |