Беси стала художницей.
Её текущая работа - решётка высоты \(N\) такая, что каждая строка решётки
содержит ровно \(M\) квадратов (\(1\le N,M\le 1000\)). Каждый квадрат или
пустой или заполнен скалой или наполнен водой. Беси уже нарисовала квадраты
заполненные скалой включая всю границу рисунка. Теперь она хочет заполнить
водой некоторые квадраты так, чтобы если бы картина стала реальностью, не было
бы движения воды. Определим высоту квадрата в \(i\)-ой строке от вершины как
\(N+1-i\). Беси хочет, чтобы её рисунок удовлетворял следующим ограничениям:
Предположим, что квадрат \(a\) заполнен водой. Тогда если существует путь из
квадрата \(a\) в квадрат \(b\) используя только пустые квадраты и квадраты с водой
которые не выше чем \(a\), такой что каждые два соседних квадрата имеют общую
сторону, тогда квадрат \(b\) тоже заполнен водой.
Определите количество различных рисунков, которые может сделать Беси
по модулю \(10^9+7\). Беси может заполнить водой любое количество квадратов
от 0 до всех включительно.
ОЦЕНИВАНИЕ:
- В тестах 1-5 \(N,M\le 10.\)
- В тестах 6-15 нет дополнительных орраничений.
ФОРМАТ ВВОДА (файл cave.in):
Первая строка ввода содержит два разделённых пробелом целых числа
\(N\) и
\(M\).
Каждая из последующих \(N\) строк ввода содержит \(M\) символов. Каждый символ
есть '.' или '#', представляющие пустой квадрат и скалу, соответственно.
Первая и последняя строки, а также первый и последний столбцы содержат только '#'.
ФОРМАТ ВЫВОДА (файл cave.out):
Одно целое число: количество рисунков, удовлетворяющих условию по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 9
#########
#...#...#
#.#...#.#
#########
|
9
|