D. Ковёр-из-домино
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

...И с вами снова... Теле-Майк!

Устали от однообразного интерьера? Надоела серая обыденность? Мечтаете о головокружительных изменениях вашей скромной обители? У нас есть, что предложить вам!

Этот Ковёр-из-домино всего за $99.99 изменит вашу жизнь! Вы можете постелить им пол, повесить его на стену или даже на потолок! Кроме всего прочего...

Вирус Хексадесимал, насмотревшись рекламы, захотела заполучить такой Ковёр-из-домино и обязательно сфотографироваться на его фоне. Но ясное дело — вирус никогда не согласится покупать лицензионный Ковёр! Поэтому она заказала грузовик домино и решила смастерить такой Ковёр сама.

Оригинальный Ковёр-из-домино представляет собой поле из квадратиков размера n × m. Каждый квадратик является половиной кости домино и может быть ориентирован либо вертикально, либо горизонтально, независимо от соседей. Вертикально ориентированные половинки домино выглядят так:

А горизонтально ориентированные вот так:

Отсюда можно заметить, что некоторые половинки выглядят одинаково в обоих положениях, а некоторые — по-разному.

Кости домино, которые купила Хексадесимал, представляют собой неразрезаемые фишки размера 1 × 2, которые можно класть либо вертикально, либо горизонтально. Если кость расположить вертикально, то обе её половинки должны быть вертикально ориентированными; если горизонтально, то обе половинки должны быть ориентированы горизонтально.

Ниже приведены правильные и неправильные примеры вертикально и горизонтально расположенных костей домино:

Вирус Хексадесимал собирает свой собственный Ковёр-из-домино так, что выполняются следующие условия:

  • каждая клетка ковра покрыта костью домино, т.е. нет пустых клеток;
  • все кости домино лежат строго внутри ковра и не накладываются друг на друга;
  • если есть горизонтальная кость домино, у которой левая половина лежит в столбце j, то нет горизонтальных костей домино, у которых левая половина лежит в столбце j - 1 или j + 1.

Прежде чем начать собирать свой собственный Ковёр-из-домино, вирус хочет узнать количество способов достичь намеченной цели по модулю 109 + 7.

Можете предполагать, что количество костей домино каждого вида у вируса бесконечно велико.

Входные данные

В первой строке даны два целых числа n и m, разделённые пробелом — размер Ковра-из-домино (1 ≤ n, m ≤ 250). В последующих 4n + 1 строках содержится 4m + 1 символов.

Каждый квадратик Ковра-из-домино — половина кости домино — описывается квадратом 3 × 3. Символ 'O' в этом квадрате обозначает наличие точки, символ '.' — её отсутствие.

Каждый квадрат 3 × 3 очерчен от соседних квадратов символами '#' так, как показано в примерах.

Гарантируется, что каждый квадратик описывает корректную половину кости домино.

Во всех претестах Ковры-из-домино имеют размер 2 × 2 и 4 × 4.

Выходные данные

Выведите одно число — количество способов собрать Ковёр-из-домино по модулю 109 + 7, пользуясь только стандартными костями домино размера 1 × 2.

Примеры
Входные данные
3 4
#################
#O..#...#O.O#...#
#.O.#.O.#.O.#...#
#..O#...#O.O#...#
#################
#O.O#OOO#O.O#...#
#.O.#...#...#.O.#
#O.O#OOO#O.O#...#
#################
#O.O#...#O.O#...#
#...#...#...#.O.#
#O.O#...#O.O#...#
#################
Выходные данные
3
Входные данные
2 2
#########
#O.O#O.O#
#.O.#...#
#O.O#O.O#
#########
#...#O.O#
#...#...#
#...#O.O#
#########
Выходные данные
2
Входные данные
2 2
#########
#..O#O..#
#...#...#
#O..#..O#
#########
#O..#..O#
#...#...#
#..O#O..#
#########
Выходные данные
0
Примечание

Пояснение к первому примеру: корректные способы собрать Ковёр-из-домино изображены ниже:

В свою очередь, следующий способ является некорректным: