Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i, j) для всех i (1 ≤ i ≤ n), j (1 ≤ j ≤ n). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:
Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x[1]
, y) и (x[2]
, y) (x[1]
≤ x[2]
) есть часть подмножества, то все ячейки (x, y) с x[1]
≤ x ≤ x[2]
также часть подмножества.
Если ячейки (x, y[1]
) и (x, y[2]
) (y[1]
≤ y[2]
) есть часть подмножества, то все ячейки (x, y) с y[1]
≤ y ≤ y[2]
также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 10^9
+ 7.
Первая строка содержит число n (1 ≤ n ≤ 150).
Каждая из последующих n строк содержит строку из n символов. j-ый символ строки i сверху равен G если ячейка (i, j) содержит траву или символ . в противном случае.
Выведите количество сбалансированных подмножеств по модулю 10^9
+ 7.
Для этого теста все 4-связные подмножества сбалансированные.
Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию: