Farmer John possède un petit champ en forme de grille de $N$ par $N$ cases ($1 \le N \le 2000$). Pour tous $1 \le i,j \le N$, la $j$-ième case en partant de la gauche dans la $i$-ième ligne en partant du haut est notée $(i,j)$. Il souhaite planter du maïs doux et de la luzerne dans son champ. Pour cela, il doit installer des arroseurs particuliers.

Un arroseur pour le maïs doux installé dans la case $(I,J)$ arrose toutes les cases situées en bas à gauche : c'est-à-dire les cases $(i,j)$ telles que $I \le i$ et $j \le J$.

Un arroseur pour la luzerne installé dans la case $(I,J)$ arrose toutes les cases situées en haut à droite : c'est-à-dire les cases $(i,j)$ telles que $i \le I$ et $J \le j$.

Une case arrosée par un ou plusieurs arroseurs pour le maïs doux peut produire du maïs doux ; une case arrosée par un ou plusieurs arroseurs pour la luzerne peut produire de la luzerne. Cependant, une case arrosée par les deux types d'arroseurs (ou par aucun des deux) ne peut rien produire.

Aidez FJ à déterminer le nombre de façons (modulo $10^9 + 7$) d'installer des arroseurs dans son champ, à raison d'au plus un par case, de sorte que chaque case soit fertile (c'est-à-dire arrosée par exactement un type d'arroseur).

Certaines cases sont déjà occupées par des vaches au pelage laineux ; cela ne les empêche pas d'être fertiles, mais aucun arroseur ne peut être installé dans ces cases.

Entrée

La première ligne contient un seul entier $N.$

Pour chaque $1\le i\le N,$ la ligne numéro $i+1$ contient une chaîne de longueur $N$ décrivant la $i$-ième ligne de la grille. Chaque caractère de cette chaîne est soit 'W' (indiquant une case occupée par une vache au pelage laineux), soit '.' (une case inoccupée).

Sortie

Affichez le reste de la division du nombre de façons d'installer les arroseurs par $10^9+7.$

Exemples

Entrée 1

2
..
..

Sortie 1

28

Remarque

Voici les quatorze possibilités lorsque du maïs doux peut pousser dans la case $(1,1)$.

CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C  
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..

Entrée 2

4
..W.
..WW
WW..
...W

Sortie 2

2304

Remarque

Cet exemple satisfait les contraintes de la première sous-tâche décrite ci-dessous.

Sous-tâches

• Les tests 3–4 satisfont $N\le 10$ et il y a au plus dix cases inoccupées.
• Les tests 5–9 satisfont $N\le 200$.
• Les tests 10–16 n'ont aucune contrainte supplémentaire.

Auteur du problème : Benjamin Qi