У Farmer John есть небольшое поле в виде сетки размером $N$ на $N$ ($1 \le N \le 2000$). Клетка, которая находится на $j$-м месте слева в $i$-й строке сверху, обозначается $(i,j)$ для всех $1 \le i,j \le N$. Он хочет выращивать на своём поле сладкую кукурузу и люцерну. Для этого ему нужно установить специальные разбрызгиватели.

Разбрызгиватель для сладкой кукурузы в клетке $(I,J)$ поливает все клетки снизу слева: то есть клетки $(i,j)$, для которых $I \le i$ и $j \le J$.

Разбрызгиватель для люцерны в клетке $(I,J)$ поливает все клетки сверху справа: то есть клетки $(i,j)$, для которых $i \le I$ и $J \le j$.

В клетке, которую поливает один или несколько разбрызгивателей для сладкой кукурузы, можно выращивать сладкую кукурузу; в клетке, которую поливает один или несколько разбрызгивателей для люцерны, можно выращивать люцерну. Но в клетке, которую поливают разбрызгиватели обоих типов (или не поливает ни один тип), ничего выращивать нельзя.

Помогите FJ определить количество способов (по модулю $10^9 + 7$) установить разбрызгиватели на его поле, не более одного в каждой клетке, так, чтобы каждая клетка была плодородной (то есть поливалась разбрызгивателями ровно одного типа).

Некоторые клетки уже заняты мохнатыми коровами; это не мешает таким клеткам быть плодородными, но устанавливать в них разбрызгиватели нельзя.

Входные данные

Первая строка содержит одно целое число $N.$

Для каждого $1\le i\le N,$ строка с номером $i+1$ содержит строку длины $N$, описывающую $i$-ю строку сетки. Каждый символ этой строки — либо 'W' (клетка занята мохнатой коровой), либо '.' (клетка свободна).

Выходные данные

Выведите остаток от деления количества способов установить разбрызгиватели на $10^9+7.$

Примеры

Входные данные 1

2
..
..

Выходные данные 1

28

Примечание

Ниже приведены все четырнадцать вариантов, в которых в клетке $(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., .., ..

Входные данные 2

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

Выходные данные 2

2304

Примечание

Этот пример удовлетворяет ограничениям первой подзадачи, описанной ниже.

Подзадачи

• В тестах 3–4 выполняется $N\le 10$, и свободных клеток не более десяти.
• В тестах 5–9 выполняется $N\le 200$.
• В тестах 10–16 дополнительных ограничений нет.

Автор задачи: Benjamin Qi