시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB219950.000%

문제

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

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

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

2

노트

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

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