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