| Codeforces Beta Round 69 (Div. 1 Only) |
|---|
| Закончено |
...И с вами снова... Теле-Майк!
Устали от однообразного интерьера? Надоела серая обыденность? Мечтаете о головокружительных изменениях вашей скромной обители? У нас есть, что предложить вам!
Этот Ковёр-из-домино всего за $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
Пояснение к первому примеру: корректные способы собрать Ковёр-из-домино изображены ниже:
В свою очередь, следующий способ является некорректным:
