O. Шлягер
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Шлягером размера $$$n$$$ называется таблица $$$n$$$ на $$$n$$$, где каждая клетка таблицы равна либо $$$1$$$, либо $$$0$$$, и нет двух соседних по сторонам клеток одновременно равных $$$1$$$. Ваша задача — посчитать количество шлягеров размера $$$n$$$.

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

В единственной строке дано натуральное число $$$n$$$ ($$$1\leq n\leq 10$$$).

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

Выведите ответ на задачу по модулю $$$10^9+7$$$.

Примеры
Входные данные
1
Выходные данные
2
Входные данные
2
Выходные данные
7