Farmer John tem um pequeno campo com a forma de uma grelha de $N$ por $N$ ($1 \le N \le 2000$), em que a $j$-ésima célula a contar da esquerda na $i$-ésima linha a contar de cima é denotada por $(i,j)$, para todos os $1 \le i,j \le N$. Ele quer plantar milho doce e alfafa no seu campo. Para isso, precisa de instalar alguns aspersores especiais.

Um aspersor de milho doce na célula $(I,J)$ rega todas as células abaixo e à esquerda: isto é, as células $(i,j)$ com $I \le i$ e $j \le J$.

Um aspersor de alfafa na célula $(I,J)$ rega todas as células acima e à direita: isto é, as células $(i,j)$ com $i \le I$ e $J \le j$.

Uma célula regada por um ou mais aspersores de milho doce pode produzir milho doce; uma célula regada por um ou mais aspersores de alfafa pode produzir alfafa. Mas uma célula regada pelos dois tipos de aspersores (ou por nenhum dos tipos) não pode produzir nada.

Ajude FJ a determinar o número de maneiras (módulo $10^9 + 7$) de instalar aspersores no seu campo, no máximo um por célula, de modo que todas as células sejam férteis (isto é, regadas por exatamente um tipo de aspersor).

Algumas células já estão ocupadas por vacas lanudas; isso não impede que essas células sejam férteis, mas não é possível instalar aspersores nelas.

Entrada

A primeira linha contém um único inteiro $N.$

Para cada $1\le i\le N,$ a linha de número $i+1$ contém uma cadeia de comprimento $N$ que representa a $i$-ésima linha da grelha. Cada caráter da cadeia é 'W' (indicando uma célula ocupada por uma vaca lanuda) ou '.' (desocupada).

Saída

Imprima o resto da divisão do número de maneiras de instalar aspersores por $10^9+7.$

Exemplos

Entrada 1

2
..
..

Saída 1

28

Nota

Aqui estão todas as catorze possibilidades em que é possível produzir milho doce em $(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

Saída 2

2304

Nota

Este exemplo satisfaz as restrições da primeira subtarefa descrita abaixo.

Subtarefas

• Os testes 3–4 satisfazem $N\le 10$ e existem, no máximo, dez células desocupadas.
• Os testes 5–9 satisfazem $N\le 200$.
• Os testes 10–16 não têm restrições adicionais.

Autor do problema: Benjamin Qi