Problem H
Abstract Painting

Gon is currently training to become a modern artist.

Abstract Painting.

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$.

3
1 1
1 2
2 1

18
108
108