Наскальные рисунки
Бесси стала художницей и рисует пещеры! Сейчас она работает над картиной высоты n, так что каждая ее строка содержит ровно m квадратов. Каждый квадрат либо пуст, либо заполнен камнем, либо заполнен водой. Бесси уже нарисовала квадраты, содержащие камень, включая всю границу картины. Теперь она хочет заполнить водой несколько пустых квадратов так, чтобы, если бы картина была настоящей, то вода не смогла бы течь по картине. Определим высоту квадрата в i - ой строке сверху равную n + 1 − i. Бесси хочет, чтобы ее картина удовлетворяла следующему ограничению:
Предположим, что квадрат a заполнен водой. Тогда если существует путь от a до квадрата b с использованием только пустых квадратов или квадратов воды, размер которых не превышает a, так что каждые два соседних квадрата на пути имеют общую сторону, тогда b тоже залит водой.
Найдите количество различных картин, которые Бесси может нарисовать по модулю 10^9 + 7. Бесси может заполнить водой любое количество пустых квадратов (все или ничего).
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1000). Каждая из следующих n строк содержит m символов. Каждый символ - это либо '.', либо '#', представляющий пустой квадрат и квадрат, заполненный камнем, соответственно. Первая и последняя строка, а также первый и последний столбцы содержат только '#'.
Выходные данные
Выведите одно целое число: количество картин, удовлетворяющих ограничению по модулю 10^9 + 7.
Пример
Если квадрат во втором ряду заполнен водой, то все пустые квадраты должны быть заполнены водой. В противном случае предположим, что такие квадраты не заполнены водой. Затем Бесси может заполнить любое подмножество из трех смежных по горизонтали областей пустыми квадратами в третьей строке. Таким образом, количество картин равно 1 + 2^3 = 9.