D. Ксюша и доминошки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ксюша очень любит пазлы, особенно ей нравятся пазлы, состоящие из доминошек. Посмотрите на рисунок, изображающий один из таких пазлов.

Пазл представляет собой таблицу размера 3 × n клеток с запрещенными клетками (черные квадраты), на которой лежат доминошки (цветные прямоугольники на рисунке). Пазл считается корректным, если выполняются следующие условия:

  • каждая доминошка занимает ровно две не запрещенные клетки таблицы;
  • никакие две доминошки не занимают одну и ту же клетку таблицы;
  • ровно одна не запрещенная клетка таблицы не занята никакой доминошкой (на рисунке отмечена кружочком).

Чтобы решить пазл нужно за несколько ходов переместить пустую клетку из начального положения в некоторое заданное. Ходом считается перемещение доминошки на пустую клетку, так чтобы пазл оставался корректным. Горизонтальные доминошки могут быть перемещены только по горизонтали, а вертикальные только по вертикали. Поворачивать доминошки не разрешается. На рисунке изображен возможный ход.

У Ксюши есть таблица размера 3 × n клеток с запрещенными клетками и помеченной кружочком клеткой. Также у Ксюши есть очень много одинаковых доминошек. Теперь Ксюша интересуется, сколько различных корректных пазлов она сможет составить, размещая доминошки на имеющейся таблице. Дополнительно Ксюша хочет, чтобы помеченная кружочком клетка была пустой в полученном пазле и чтобы в пазле существовал хотя бы один ход.

Помогите Ксюше, посчитайте описанное количество пазлов. Так как описанное количество может быть достаточно большим, выведите его остаток от деления на число 1000000007 (109 + 7).

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

В первой строке записано целое число n (3 ≤ n ≤ 104) — размер пазла. В каждой из следующих трех строк записаны по n символов — описание имеющейся таблицы. Символ номер j строки номер i равен «X», если соответствующая клетка запрещенная; равен «.», если соответствующая клетка не запрещенная, равен «O», если соответствующая клетка помечена кружочком.

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

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

Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).

Примеры
Входные данные
5
....X
.O...
...X.
Выходные данные
1
Входные данные
5
.....
.O...
.....
Выходные данные
2
Входные данные
3
...
...
..O
Выходные данные
4
Примечание

Два пазла считаются различными, если существует пара клеток, занятых в одном из них одной доминошкой, а в другом — нет.