F. Охранники на складе
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп — директор магазина в столице Берляндии. Недавно уровень преступности в столице возрос, поэтому Поликарп озаботился охраной склада своего магазина.

Склад можно представить как матрицу из n строк и m столбцов. Каждый элемент матрицы — либо . (пустая клетка), либо x (стена).

Поликарп хочет нанять некоторое количество охранников (возможно, ни одного) на склад. Каждый охранник будет стоять в какой-то клетке и наблюдать за клетками справа и снизу от него (до ближайшей стены). Формально, если охранник стоит в клетке (x0, y0), то он охраняет клетку (x1, y1), если выполняются все следующие условия:

  • (x1, y1) — пустая клетка;
  • либо x0 = x1 и y0 ≤ y1, либо x0 ≤ x1 и y0 = y1;
  • между клетками (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), и два охранника в обеих клетках.