Задачі
Викладення плитки
Викладення плитки
Скількома способами можна замостити $3 \times n$ прямокутник за допомогою $2 \times 1$ кісток доміно? Нижче наведено приклад замощення такими плитками прямокутника $3 \times 12$.
\includegraphics{https://static.e-olymp.com/content/eb/eb1f59e1a236e586e215416266f75eef921f6cc0.jpg}
\InputFile
Складаються з декількох тестів, які завершуються рядком, що містить $-1$. Кожен тест розміщено в окремому рядку і містить єдине ціле число $n~(0 \le n \le 30)$.
\OutputFile
Для кожного тесту в окремому рядку виведіть кількість способів замощення.
Вхідні дані #1
2 8 12 -1
Вихідні дані #1
3 153 2131