Draw and paint

Shadow is interested in the four-color theorem, now he wants to draw some lines on a rectangle paper to divide it into some parts, and then paint these parts with four different colors, the color of two adjacent parts must be different.
Firstly, Shadow draws a horizontal line and divides the paper into two parts (The height and width of two parts must be integer), then he paints one part with a kind of color.
Then he draws a vertical line and divides the other part into two parts (The height and width of two parts must be integer), then he paints one part with a kind of color.
Then he draws a horizontal line……That is to say, Shadow draws a horizontal line during an odd step, and a vertical line during an even step. Shadow repeats these operations until he can’t or doesn’t want to anymore.
Shadow can’t rotate or overturn the paper, do you know how many different ways can he draw lines and paint colors.

The first line is one integer T indicates the number of test cases. (T <= 1000)
Then for each test case, there are two integers n and m ( 0 < n,m <= 40 )in one line, indicates the height and width of the rectangle paper.

For each test case,output one integer in a line, the amount of ways can Shadow draw and paint mod 1000000007.

3
1 1
1 2
2 1

4
4
16

FZU

2012 Multi-University Training Contest 7