Bipartite Grid Coloring

You are given a grid of size (n \times m) that needs to be colored with two colors. The coloring must be done in such a way that no two adjacent cells (sharing a common side) have the same color. It is known that a valid coloring exists only when at least one of the grid dimensions is even. In such cases, there are exactly 2 ways to color the grid (corresponding to swapping the two colors). Otherwise, if both (n) and (m) are odd, no valid coloring exists and the answer is 0. All answers should be computed modulo (10^9+7).

inputFormat

The first line of input contains a single integer (T), the number of test cases. Each of the next (T) lines contains two positive integers (n) and (m) representing the dimensions of the grid.

outputFormat

For each test case, output a single line containing the number of valid ways to color the grid according to the rules, computed modulo (10^9+7).## sample

3
2 2
3 3
1 2

2
0
2