eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сбалансированные подмножества

Сбалансированные подмножества

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i, j) для всех i (1in), j (1jn). Некоторые из этих ячеек содержат траву.

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

  • Все ячейки подмножества содержат траву.

  • Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.

  • Если ячейки (x[1], y) и (x[2], y) (x[1]x[2]) есть часть подмножества, то все ячейки (x, y) с x[1]xx[2] также часть подмножества.

  • Если ячейки (x, y[1]) и (x, y[2]) (y[1]y[2]) есть часть подмножества, то все ячейки (x, y) с y[1]yy[2] также часть подмножества.

Посчитайте количество сбалансированных подмножеств по модулю 10^9 + 7.

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

Первая строка содержит число n (1n150).

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

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

Выведите количество сбалансированных подмножеств по модулю 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
GG
GG
Выходные данные #1
13
Входные данные #2
4
GGGG
GGGG
GG.G
GGGG
Выходные данные #2
642
Источник 2021 USACO US Open, Платина