Збалансовані підмножини#11242

Збалансовані підмножини

2 секунди

128 мегабайтів

Дуже складна

Пасовище Фермера Джона можна уявити як велику 2D-решітку комірок, позначених впорядкованими парами $(i, j)$ для всіх $i (1 \leq i \leq n), j (1 \leq j \leq n)$ i~(1 \le i \le n), j~(1 \le j \le n). Деякі з цих комірок містять траву.

Непорожня підмножина комірок решітки називається "збалансованою", якщо виконуються такі умови:

- Усі комірки підмножини містять траву. - Підмножина є $4$ -зв'язною. Це означає, що існує шлях з будь-якої комірки підмножини до будь-якої іншої комірки підмножини, причому дві послідовні комірки шляху є сусідніми горизонтально або вертикально. - Якщо комірки $(x_{1}, y)$ (x_1, y) і $(x_{2}, y)$ (x_2, y) ( $x_{1} \leq x_{2}$ x_1 \le x_2) належать підмножині, то всі комірки $(x, y)$ з $x_{1} \leq x \leq x_{2}$ x_1 \le x \le x_2 також належать підмножині. - Якщо комірки $(x, y_{1})$ (x, y_1) і $(x, y_{2})$ (x, y_2) ( $y_{1} \leq y_{2}$ y_1 \le y_2) належать підмножині, то всі комірки $(x, y)$ з $y_{1} \leq y \leq y_{2}$ y_1 \le y \le y_2 також належать підмножині.

Порахуйте кількість збалансованих підмножин за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Перший рядок містить число $n (1 \leq n \leq 150)$ n~(1 \le n \le 150).

Кожен з наступних $n$ рядків містить рядок з $n$ символів. $j$ -ий символ рядка $i$ зверху дорівнює $G$ , якщо комірка $(i, j)$ містить траву, або символу $.$ в іншому випадку.

Вихідні дані

Виведіть кількість збалансованих підмножин за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1. Для цього тесту всі $4$ -зв'язні підмножини є збалансованими.

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

Приклад 2. Нижче наведено приклад підмножини, яка задовольняє другій умові ( $4$ -зв'язності), але не задовольняє третій умові:

GG..
.G..
GG..
....

Приклад 1

Приклад 2