У фермера Джона есть небольшое поле в форме сетки n на n, где j - ый квадрат слева от i - го ряда сверху - обозначается (i, j) для всех 1 ≤ i, j ≤ n. Он заинтересован в выращивании сладкой кукурузы и люцерны на своем поле. Для этого ему необходимо установить специальные оросители.

Распылитель сладкой кукурузы в квадрате (I, J) опрыскивает все квадраты в нижнем левом углу: то есть (i, j) с I ≤ i и j ≤ J.

Распылитель люцерны в квадрате (I, J) опрыскивает все квадраты в правом верхнем углу: то есть (i, j) с i ≤ I и J ≤ j.

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

Помогите ФД определить количество способов (по модулю 109 + 7) установки спринклеров на его поле, не более одного на квадрат, чтобы каждый квадрат был плодородным (то есть опрыскивался ровно одним типом спринклера).

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

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

Первая строка содержит единственное целое число n (1 ≤ n ≤ 2000). Для каждого i (1 ≤ i ≤ n) i + 1 - ая строка содержит строку длины n и обозначает i - ую строку сетки. Каждый символ строки представляет собой один 'W' (обозначает квадрат, занятый шерстистой коровой) или '.' (незанятый квадрат).

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

Выведите остаток от деления количества способов установки оросителей на 109 + 7.

Пример

Вот все четырнадцать возможностей, когда сладкая кукуруза может расти в (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., .., ..