Сапёр 1D
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сапёр — это игра на клетчатом поле, цель которой — найти расположение всех мин. Изначально все клетки поля скрыты. Нажатие на клетку её открывает, и если там находится мина — игрок тут же проигрывает. Если же в клетке нет мины, то в ней показывается число — суммарное количество мин в соседних клетках. Соседними считаются восемь смежных клеток по диагонали.

Игра Сапёр — не тривиальная, и часто в ней невозможно выиграть наверняка. Давайте рассмотрим упрощённую версию: одномерный Сапёр. Она играется на поле с всего двумя строчками, размера $$$2 \times N$$$. В первой строки расположены мины, а вторая строка пустая. Таким образом, каждая клетка второй строки всегда может быть открыта, и в ней записано число от $$$0$$$ до $$$3$$$ — количество мин в трёх соседних клетках первой строки (двух в случае крайних клеток).

Вот пример поля одномерного Сапёра ширины $$$6$$$:

Проблема в том, что даже в одномерном Сапёре решение не всегда можно гарантированно найти. Мы предлагаем вам для каждого $$$N$$$ посчитать количество возможный полей ширины $$$N$$$, которые можно гарантированно решить, не полагаясь на удачу.

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

В единственной строке дано одно целое число $$$N$$$ — ширина поля ($$$1 \le N \le 10^5$$$).

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

Выведите единственное число — количество различных полей размера $$$2 \times N$$$, которые можно гарантированно решить, по модулю $$$10^9 + 7$$$. Иными словами, если $$$x$$$ — количество таких полей, выведите $$$x \mod 10^9 + 7$$$. Два поля считаются различными, если мины в них расположены не на одних и тех же местах.

Примеры

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

Примечание

Во втором примере есть два поля, которые можно гарантированно решить:

Есть два других поля ширины $$$2$$$, но их невозможно отличить друг от друга просто посмотрев на нижний ряд: