26063번 - Сапёр 1D 다국어

문제

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

Игра Сапёр --- не тривиальная, и часто в ней невозможно выиграть наверняка. Давайте рассмотрим упрощённую версию: одномерный Сапёр. Она играется на поле с всего двумя строчками, размера 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$. Два поля считаются различными, если мины в них расположены не на одних и тех же местах.

제한

노트

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

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