Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Probablemente usted esté leyendo este problema porque es el más corto, pero no se asuste por el título y no vaya a pensar que el problema está relacionado con Álgebra. Además no se apresure, si usted no domina el arte de contar le recomiendo que cambie de problema.

El problema consiste en calcular la cantidad de formas de rellenar una matriz de $M \times N$ con $1$ o $-1$ en cada casilla, de forma tal que el producto de los números en cada fila y en cada columna sea $-1$.

Input

Línea 1: Un entero $T$ $(1 \leq T \leq 500000)$ indicando la cantidad de casos.
Línea 2 ... T + 1: Dos enteros por línea $M$ y $N$ $(1 \leq M, N \leq 1000)$ representando las dimensiones de la matriz para el caso correspondiente.

Output

Línea 1 ... T: Un entero por línea indicando la cantidad de formas de rellenar la matriz del caso correspondiente módulo $1000000007$.

Sample test(s)