Farmer John ha un piccolo campo a forma di griglia di $N$ per $N$ celle ($1 \le N \le 2000$), in cui la $j$-esima cella da sinistra della $i$-esima riga dall'alto è indicata con $(i,j)$ per ogni $1 \le i,j \le N$. Vuole coltivare mais dolce ed erba medica nel suo campo. Per farlo, deve installare alcuni irrigatori speciali.

Un irrigatore per il mais dolce nella cella $(I,J)$ irriga tutte le celle in basso a sinistra: cioè le celle $(i,j)$ con $I \le i$ e $j \le J$.

Un irrigatore per l'erba medica nella cella $(I,J)$ irriga tutte le celle in alto a destra: cioè le celle $(i,j)$ con $i \le I$ e $J \le j$.

In una cella irrigata da uno o più irrigatori per il mais dolce può crescere il mais dolce; in una cella irrigata da uno o più irrigatori per l'erba medica può crescere l'erba medica. Ma in una cella irrigata da entrambi i tipi di irrigatori (o da nessuno dei due) non può crescere nulla.

Aiuta FJ a determinare il numero di modi (modulo $10^9 + 7$) di installare gli irrigatori nel suo campo, al massimo uno per cella, in modo che ogni cella sia fertile (cioè irrigata da esattamente un tipo di irrigatore).

Alcune celle sono già occupate da mucche lanose; questo non impedisce a tali celle di essere fertili, ma non è possibile installarvi irrigatori.

Input

La prima riga contiene un solo intero $N.$

Per ogni $1\le i\le N,$ la $i+1$-esima riga contiene una stringa di lunghezza $N$ che rappresenta la $i$-esima riga della griglia. Ogni carattere della stringa è 'W' (che indica una cella occupata da una mucca lanosa) oppure '.' (non occupata).

Output

Stampa il resto della divisione del numero di modi di installare gli irrigatori per $10^9+7.$

Esempi

Input 1

2
..
..

Output 1

28

Nota

Ecco tutte le quattordici possibilità quando il mais dolce può crescere in $(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., .., ..

Input 2

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

Output 2

2304

Nota

Questo soddisfa i vincoli del primo sottoproblema descritto di seguito.

Sottoproblemi

• I casi di test 3–4 soddisfano $N\le 10$ e ci sono al massimo dieci celle non occupate.
• I casi di test 5–9 soddisfano $N\le 200$.
• I casi di test 10–16 non hanno vincoli aggiuntivi.

Autore del problema: Benjamin Qi