Ксюша очень любит пазлы, особенно ей нравятся пазлы, состоящие из доминошек. Посмотрите на рисунок, изображающий один из таких пазлов.
Пазл представляет собой таблицу размера 3 × n клеток с запрещенными клетками (черные квадраты), на которой лежат доминошки (цветные прямоугольники на рисунке). Пазл считается корректным, если выполняются следующие условия:
- каждая доминошка занимает ровно две не запрещенные клетки таблицы;
- никакие две доминошки не занимают одну и ту же клетку таблицы;
- ровно одна не запрещенная клетка таблицы не занята никакой доминошкой (на рисунке отмечена кружочком).
Чтобы решить пазл нужно за несколько ходов переместить пустую клетку из начального положения в некоторое заданное. Ходом считается перемещение доминошки на пустую клетку, так чтобы пазл оставался корректным. Горизонтальные доминошки могут быть перемещены только по горизонтали, а вертикальные только по вертикали. Поворачивать доминошки не разрешается. На рисунке изображен возможный ход.
У Ксюши есть таблица размера 3 × n клеток с запрещенными клетками и помеченной кружочком клеткой. Также у Ксюши есть очень много одинаковых доминошек. Теперь Ксюша интересуется, сколько различных корректных пазлов она сможет составить, размещая доминошки на имеющейся таблице. Дополнительно Ксюша хочет, чтобы помеченная кружочком клетка была пустой в полученном пазле и чтобы в пазле существовал хотя бы один ход.
Помогите Ксюше, посчитайте описанное количество пазлов. Так как описанное количество может быть достаточно большим, выведите его остаток от деления на число 1000000007 (109 + 7).
Примечание
Два пазла считаются различными, если существует пара клеток, занятых в одном из них одной доминошкой, а в другом — нет.