Farmer John besitzt ein kleines Feld in Form eines $N$ mal $N$ großen Gitters ($1 \le N \le 2000$). Für alle $1 \le i,j \le N$ wird das $j$-te Feld von links in der $i$-ten Zeile von oben mit $(i,j)$ bezeichnet. Er möchte auf seinem Feld Zuckermais und Luzerne anbauen. Dazu muss er einige spezielle Sprinkler installieren.

Ein Zuckermais-Sprinkler im Feld $(I,J)$ bewässert alle Felder links unterhalb davon, also alle $(i,j)$ mit $I \le i$ und $j \le J$.

Ein Luzerne-Sprinkler im Feld $(I,J)$ bewässert alle Felder rechts oberhalb davon, also alle $(i,j)$ mit $i \le I$ und $J \le j$.

Auf einem Feld, das von einem oder mehreren Zuckermais-Sprinklern bewässert wird, kann Zuckermais wachsen; auf einem Feld, das von einem oder mehreren Luzerne-Sprinklern bewässert wird, kann Luzerne wachsen. Auf einem Feld, das von beiden Sprinklertypen bewässert wird (oder von keinem), kann jedoch nichts wachsen.

Hilf FJ, die Anzahl der Möglichkeiten (modulo $10^9 + 7$) zu bestimmen, Sprinkler auf seinem Feld zu installieren, höchstens einen pro Feld, sodass jedes Feld fruchtbar ist (also von genau einem Sprinklertyp bewässert wird).

Einige Felder sind bereits von zotteligen Kühen besetzt. Das hindert diese Felder nicht daran, fruchtbar zu sein, aber auf solchen Feldern können keine Sprinkler installiert werden.

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $N.$

Für jedes $1\le i\le N,$ enthält die $(i+1)$-te Zeile eine Zeichenkette der Länge $N$, die die $i$-te Zeile des Gitters beschreibt. Jedes Zeichen ist entweder 'W' (ein von einer zotteligen Kuh besetztes Feld) oder '.' (ein unbesetztes Feld).

Ausgabe

Gib den Rest aus, der bei der Division der Anzahl der Möglichkeiten zur Installation der Sprinkler durch $10^9+7.$ entsteht.

Beispiele

Eingabe 1

2
..
..

Ausgabe 1

28

Hinweis

Hier sind alle vierzehn Möglichkeiten, bei denen auf $(1,1)$ Zuckermais wachsen kann.

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., .., ..

Eingabe 2

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

Ausgabe 2

2304

Hinweis

Dies erfüllt die Beschränkungen der unten beschriebenen ersten Teilaufgabe.

Teilaufgaben

• Die Testfälle 3-4 erfüllen $N\le 10$, und es gibt höchstens zehn unbesetzte Felder.
• Die Testfälle 5-9 erfüllen $N\le 200$.
• Für die Testfälle 10-16 gelten keine zusätzlichen Beschränkungen.

Autor der Aufgabe: Benjamin Qi