Сапёр 1D

문제

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

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

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

[이미지 1]

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

입력

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

출력

Выведите единственное число --- количество различных полей размера $2\times N2\; \backslash times\; N$, которые можно гарантированно решить, по модулю ${10}^9+710^9\; +\; 7$. Иными словами, если $xx$ --- количество таких полей, выведите $x\mathrm{m}\mathrm{o}\mathrm{d}{10}^9+7x\; \backslash mod\; 10^9\; +\; 7$. Два поля считаются различными, если мины в них расположены не на одних и тех же местах.

힌트

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

[이미지 2]

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

[이미지 3]