У Фермера Джона есть маленькое поле в виде решётки \(N\) by \(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\) b \(J \le j\).
На квадрате до которого достаёт один или более разбрызгиватель для пшеницы
может расти пшеница, на квадрате до которого достаёт один или более разбрызгиватель
для люцерны может расти люцерна. На квадрате, до которого достают оба типа разбрызгивателей
(или ни одного типа разбрызгивателей) не может расти ничего.
Помогите ФД определить количество способов (по модулю \(10^9 + 7\)) установить
разбрызгиватели на своём поле, не более одного на квадрат, так, что каждый квадрат
будет доставаться только одним типом разбрызгивателя (каждый квадрат будет фертильным).
Некоторые квадраты уже занят коровами, это не запрещает квадрату быть фертильным,
но в них не могут быть установлены разбрызгиватели.
ФОРМАТ ВВОДА (файл sprinklers2.in):
Первая строка ввода содержит одно целое число
\(N.\)
Для каждого h \(1\le i\le N,\) \(i+1\)-ая строка содержит строку длиной \(N\)
обозначающую \(i\)-ую строку решётки. Каждый символ строки один из следующих:
'W' (корова), или '.' (свободный квадрат).
ФОРМАТ ВЫВОДА (файл sprinklers2.out):
Выведите остаток отделения на \(10^9+7\) количества способов установить разбрызгиватели.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
..
..
|
28
|