Busy Beaver encontró un rompecabezas extraño. El rompecabezas consiste en una caja dividida en una cuadrícula de $N \times M$ cuadrados. Cada celda de la cuadrícula está ocupada (denotada por '#'), vacía (denotada por '.') o vacía pero marcada con una 'o'.

El rompecabezas viene con un conjunto de piezas de L-tromino, una por cada celda 'o' de la cuadrícula. Un L-tromino está compuesto por tres bloques cuadrados en forma de L, como se muestra. El centro del L-tromino es el cuadrado que es adyacente a los otros dos cuadrados (marcados con una o en la imagen).

Busy Beaver se da cuenta de que para resolver el rompecabezas, necesita colocar todos los L-trominos en la caja de tal manera que los L-trominos estén alineados con la cuadrícula, el centro de cada L-tromino esté en una celda vacía marcada con una 'o' y ningún par de L-trominos se superponga entre sí o con una celda ocupada. Todos los L-trominos pueden rotarse libremente.

¿Puedes ayudar a Busy Beaver a contar el número de formas de resolver el rompecabezas? Como la respuesta puede ser grande, entrégala módulo $10^9 + 7$.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $T$ ($1 \leq T \leq 500$). A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $N$ y $M$ ($2 \leq N, M \leq 1000$), las dimensiones de la cuadrícula.

Las siguientes $N$ líneas contienen cada una $M$ caracteres, describiendo una fila de la cuadrícula. Cada carácter es '#', '.' o 'o'.

Se garantiza que la suma de $N$ sobre todos los casos de prueba no excede 1000. Se garantiza que la suma de $M$ sobre todos los casos de prueba no excede 1000.

Salida

Para cada caso de prueba, imprime un solo entero: el número de formas de resolver el rompecabezas módulo $10^9 + 7$.

Puntuación

Let $(r, c)$ denote the cell at row $r$ and column $c$ ($1 \leq r \leq N, 1 \leq c \leq M$).

• (10 puntos) Cada celda 'o' está a una distancia de Manhattan de al menos 3 de cualquier otra celda 'o'. Es decir, si $(r_1, c_1)$ y $(r_2, c_2)$ son dos celdas 'o' diferentes, entonces $|r_1 - r_2| + |c_1 - c_2| \geq 3$.
• (30 puntos) Cada celda 'o' es verticalmente adyacente a al menos otra celda 'o' o '#'. Es decir, para cualquier celda 'o' en $(r, c)$, ya sea $(r - 1, c)$ o $(r + 1, c)$ es una celda '#' u otra celda 'o'.
• (60 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

5
4 5
###.o
.o...
#..o.
#..##
5 5
..###
.o..#
.o.o.
..#o.
###..
8 31
.########.#..oo..o..o#o..o....o
o.######.o#o...o..o..#..o..oo..
o..####.o.#####..########o..###
..o.o..o..#####.o########..o###
.o##..##.o#####o.########..o###
o.##.o##.o#####..########o..###
..######..#..o..o.o..####..o###
.o######o.#o..o..o..o####o..###
2 3
#.o
.o.
2 2
..
..

Salida 1

4
6
1
0
1

Nota

Note que el primer caso de prueba satisface las restricciones de la primera subtarea y el segundo caso de prueba satisface las restricciones de la segunda subtarea.

En el primer caso de prueba, las 4 formas de resolver el rompecabezas son como se muestra:

En el segundo caso de prueba, las 6 formas de resolver el rompecabezas son como se muestra:

En el tercer caso de prueba, la única forma de resolver el rompecabezas es como se muestra:

En el cuarto caso de prueba, no hay formas de resolver el rompecabezas.

En el quinto caso de prueba, no hay celdas 'o', por lo que la forma única de resolver el rompecabezas es no colocar ningún L-tromino.