Оросителі 2: Повернення люцерни
У фермера Джона є невелике поле у формі сітки розміром 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.
Квадрат, обприсканий одним або кількома розпилювачами солодкої кукурудзи, підходить для вирощування солодкої кукурудзи; квадрат, обприсканий одним або кількома розпилювачами люцерни, підходить для вирощування люцерни. Однак, якщо квадрат обприсканий обома типами розпилювачів (або жодним з них), на ньому нічого не виросте.
Допоможіть фермеру Джону визначити кількість способів (за модулем 10^9 + 7) розміщення розпилювачів на його полі, не більше одного на квадрат, так, щоб кожен квадрат був родючим (тобто обприскувався рівно одним типом розпилювача).
Деякі квадрати вже зайняті шерстистими коровами; це не заважає цим площам бути родючими, але на таких квадратах не можна встановлювати розпилювачі.
Вхідні дані
Перша строка містить єдине ціле число n (1 ≤ n ≤ 2000). Для кожного i (1 ≤ i ≤ n) i + 1-ий рядок містить рядок довжини n, що представляє i-ий рядок сітки. Кожен символ рядка є або 'W' (означає квадрат, зайнятий шерстистою коровою), або '.' (незайнятий квадрат).
Вихідні дані
Виведіть залишок від ділення кількості способів встановлення розпилювачів на 10^9 + 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., .., ..