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

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

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

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

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

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