Busy Beaver a trouvé un puzzle étrange. Le puzzle consiste en une boîte divisée en une grille de $N \times M$ carrés. Chaque cellule de la grille est soit occupée (notée par un « # »), vide (notée par un « . »), soit vide mais marquée par un « o ».

Le puzzle est fourni avec un ensemble de pièces en forme de L-tromino, une pour chaque cellule « o » de la grille. Un L-tromino est composé de trois blocs carrés en forme de L, comme illustré. Le centre du L-tromino est le carré qui est adjacent aux deux autres carrés (marqué par un o sur l'image).

Busy Beaver réalise que pour résoudre le puzzle, il doit placer tous les L-trominos dans la boîte de telle sorte que les L-trominos soient alignés avec la grille, que chaque centre de L-tromino soit sur une cellule vide marquée par un « o », et qu'aucun L-tromino ne chevauche un autre ou une cellule occupée. Tous les L-trominos peuvent être tournés librement.

Pouvez-vous aider Busy Beaver à compter le nombre de façons de résoudre le puzzle ? Comme la réponse peut être grande, donnez-la modulo $10^9 + 7$.

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $T$ ($1 \leq T \leq 500$). La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $N$ et $M$ ($2 \leq N, M \leq 1000$), les dimensions de la grille.

Les $N$ lignes suivantes contiennent chacune $M$ caractères, décrivant une ligne de la grille. Chaque caractère est soit « # », « . », ou « o ».

Il est garanti que la somme de $N$ sur tous les cas de test ne dépasse pas 1000. Il est garanti que la somme de $M$ sur tous les cas de test ne dépasse pas 1000.

Sortie

Pour chaque cas de test, affichez un seul entier : le nombre de façons de résoudre le puzzle modulo $10^9 + 7$.

Sous-tâches

Soit $(r, c)$ la cellule à la ligne $r$ et à la colonne $c$ ($1 \leq r \leq N, 1 \leq c \leq M$).

• (10 points) Chaque cellule « o » est à une distance de Manhattan d'au moins 3 de toute autre cellule « o ». C'est-à-dire que si $(r_1, c_1)$ et $(r_2, c_2)$ sont deux cellules « o » différentes, alors $|r_1 - r_2| + |c_1 - c_2| \geq 3$.
• (30 points) Chaque cellule « o » est verticalement adjacente à au moins une autre cellule « o » ou « # ». C'est-à-dire que pour toute cellule « o » en $(r, c)$, soit $(r - 1, c)$ ou $(r + 1, c)$ est une cellule « # » ou une autre cellule « o ».
• (60 points) Aucune contrainte supplémentaire.

Exemples

Entrée 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..###
2 3
#.o
.o.
2 2
..
..

Sortie 1

4
6
1
0
1

Remarque

Notez que le premier cas de test satisfait les contraintes de la première sous-tâche et le deuxième cas de test satisfait les contraintes de la deuxième sous-tâche.

Dans le premier cas de test, les 4 façons de résoudre le puzzle sont illustrées ci-dessous :

Dans le deuxième cas de test, les 6 façons de résoudre le puzzle sont illustrées ci-dessous :

Dans le troisième cas de test, la seule façon de résoudre le puzzle est illustrée ci-dessous :

Dans le quatrième cas de test, il n'y a aucune façon de résoudre le puzzle.

Dans le cinquième cas de test, il n'y a aucune cellule « o », donc la seule façon de résoudre le puzzle est de ne placer aucun L-tromino.