Farmer John tiene un pequeño campo con forma de cuadrícula de $N$ por $N$ ($1 \le N \le 2000$), donde la $j$-ésima casilla desde la izquierda de la $i$-ésima fila desde arriba se denota por $(i,j)$ para todo $1 \le i,j \le N$. Quiere plantar maíz dulce y alfalfa en su campo. Para ello, necesita instalar unos aspersores especiales.

Un aspersor de maíz dulce en la casilla $(I,J)$ regará todas las casillas hacia abajo y a la izquierda: es decir, las casillas $(i,j)$ con $I \le i$ y $j \le J$.

Un aspersor de alfalfa en la casilla $(I,J)$ regará todas las casillas hacia arriba y a la derecha: es decir, las casillas $(i,j)$ con $i \le I$ y $J \le j$.

Una casilla regada por uno o varios aspersores de maíz dulce puede producir maíz dulce; una casilla regada por uno o varios aspersores de alfalfa puede producir alfalfa. Pero una casilla regada por ambos tipos de aspersores (o por ninguno) no puede producir nada.

Ayuda a FJ a determinar el número de maneras (módulo $10^9 + 7$) de instalar aspersores en su campo, como máximo uno por casilla, de modo que todas las casillas sean fértiles (es decir, estén regadas por exactamente un tipo de aspersor).

Algunas casillas ya están ocupadas por vacas lanudas; esto no impide que esas casillas sean fértiles, pero no se pueden instalar aspersores en ellas.

Entrada

La primera línea contiene un único entero $N.$

Para cada $1\le i\le N,$ la línea $i+1$ contiene una cadena de longitud $N$ que representa la $i$-ésima fila de la cuadrícula. Cada carácter de la cadena es 'W' (que indica una casilla ocupada por una vaca lanuda) o '.' (una casilla desocupada).

Salida

Imprime el resto de dividir el número de maneras de instalar aspersores entre $10^9+7.$

Ejemplos

Entrada 1

2
..
..

Salida 1

28

Nota

Estas son las catorce posibilidades en las que puede crecer maíz dulce en $(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., .., ..

Entrada 2

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

Salida 2

2304

Nota

Este ejemplo satisface las restricciones de la primera subtarea descrita a continuación.

Subtareas

• Los casos de prueba 3–4 satisfacen $N\le 10$ y hay como máximo diez casillas desocupadas.
• Los casos de prueba 5–9 satisfacen $N\le 200$.
• Los casos de prueba 10–16 no tienen restricciones adicionales.

Autor del problema: Benjamin Qi