Educational Codeforces Round 27 |
---|
Закончено |
Поликарп — директор магазина в столице Берляндии. Недавно уровень преступности в столице возрос, поэтому Поликарп озаботился охраной склада своего магазина.
Склад можно представить как матрицу из n строк и m столбцов. Каждый элемент матрицы — либо . (пустая клетка), либо x (стена).
Поликарп хочет нанять некоторое количество охранников (возможно, ни одного) на склад. Каждый охранник будет стоять в какой-то клетке и наблюдать за клетками справа и снизу от него (до ближайшей стены). Формально, если охранник стоит в клетке (x0, y0), то он охраняет клетку (x1, y1), если выполняются все следующие условия:
Охранники могут стоять только в пустых клетках (и охранять только пустые клетки). План охраны — некоторое множество клеток, в которых должны стоять охранники (естественно, два плана различны, если существует клетка, которая присутствует только в одном из планов). Поликарп называет план подходящим, если существует не более чем одна пустая клетка, которую никто не охраняет.
Поликарп хочет узнать количество подходящих планов. Так как оно может быть очень большим, выведите его по модулю 109 + 7.
В первой строке записаны два числа n и m — длина и ширина склада (1 ≤ n, m ≤ 250, 1 ≤ nm ≤ 250).
Затем следуют n строк, i-я из которых содержит m символов и соответствует i-й строке матрицы. Каждый символ — либо ., либо x.
Выведите количество подходящих планов по модулю 109 + 7.
1 3
.x.
3
2 2
xx
xx
1
2 2
..
..
10
3 1
x
.
x
2
В первом примере есть три возможных плана: один охранник в клетке (1, 1), один охранник в клетке (1, 3), и два охранника в обеих клетках.
Название |
---|