Hide

Problem C
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.

\includegraphics[width=0.5\textwidth ]{figure2.jpg}

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

Please log in to submit a solution to this problem

Log in