Шлягером размера $$$n$$$ называется таблица $$$n$$$ на $$$n$$$, где каждая клетка таблицы равна либо $$$1$$$, либо $$$0$$$, и нет двух соседних по сторонам клеток одновременно равных $$$1$$$. Ваша задача — посчитать количество шлягеров размера $$$n$$$.
В единственной строке дано натуральное число $$$n$$$ ($$$1\leq n\leq 10$$$).
Выведите ответ на задачу по модулю $$$10^9+7$$$.
1
2
2
7
