Farmer John ma niewielkie pole w kształcie siatki $N$ na $N$ ($1 \le N \le 2000$). Dla wszystkich $1 \le i,j \le N$ pole w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej oznaczamy przez $(i,j)$. Chciałby uprawiać na swoim polu kukurydzę cukrową i lucernę. W tym celu musi zainstalować specjalne zraszacze.

Zraszacz kukurydzy cukrowej w polu $(I,J)$ podlewa wszystkie pola na lewo i poniżej niego, czyli pola $(i,j)$ spełniające $I \le i$ oraz $j \le J$.

Zraszacz lucerny w polu $(I,J)$ podlewa wszystkie pola na prawo i powyżej niego, czyli pola $(i,j)$ spełniające $i \le I$ oraz $J \le j$.

Na polu podlewanym przez jeden lub więcej zraszaczy kukurydzy cukrowej może rosnąć kukurydza cukrowa; na polu podlewanym przez jeden lub więcej zraszaczy lucerny może rosnąć lucerna. Jednak na polu podlewanym przez oba rodzaje zraszaczy (lub przez żaden z nich) nie może rosnąć nic.

Pomóż FJ wyznaczyć liczbę sposobów (modulo $10^9 + 7$) zainstalowania zraszaczy na jego polu, najwyżej jednego na każdym polu siatki, tak aby każde pole było żyzne (czyli podlewane przez dokładnie jeden rodzaj zraszacza).

Niektóre pola są już zajęte przez włochate krowy. Nie przeszkadza to tym polom być żyznymi, ale nie można na nich instalować zraszaczy.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $N$.

Dla każdego $1\le i\le N$ wiersz $i+1$ zawiera napis długości $N$, opisujący $i$-ty wiersz siatki. Każdy znak napisu to 'W' (pole zajęte przez włochatą krowę) albo '.' (pole niezajęte).

Wyjście

Wypisz resztę z dzielenia liczby sposobów zainstalowania zraszaczy przez $10^9+7$.

Przykład

Wejście 1

2
..
..

Wyjście 1

28

Uwagi

Oto wszystkie czternaście możliwości, w których kukurydza cukrowa może rosnąć na polu $(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., .., ..

Wejście 2

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

Wyjście 2

2304

Uwagi

Ten przykład spełnia ograniczenia pierwszego podzadania opisanego poniżej.

Podzadania

• Testy 3-4 spełniają $N\le 10$, a niezajętych pól jest najwyżej dziesięć.
• Testy 5-9 spełniają $N\le 200$.
• Testy 10-16 nie mają dodatkowych ograniczeń.

Autor zadania: Benjamin Qi