Сбалансированные подмножества
Сбалансированные подмножества
Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i, j) для всех i (1 ≤ i ≤ n), j (1 ≤ j ≤ n). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:
- Все ячейки подмножества содержат траву.
- Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
- Если ячейки (
x1
, y) и (x2
, y) (x1
≤x2
) есть часть подмножества, то все ячейки (x, y) сx1
≤ x ≤x2
также часть подмножества. - Если ячейки (x,
y1
) и (x,y2
) (y1
≤y2
) есть часть подмножества, то все ячейки (x, y) сy1
≤ y ≤y2
также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 109
+ 7.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 150).
Каждая из последующих n строк содержит строку из n символов. j-ый символ строки i сверху равен G если ячейка (i, j) содержит траву или символ . в противном случае.
Выходные данные
Выведите количество сбалансированных подмножеств по модулю 109
+ 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..
....
2 GG GG
13
4 GGGG GGGG GG.G GGGG
642