Стільники

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

Є стільники. Бджілка може ходити так, як показано на рисунку — ходами $1$ і $2$ з верхнього ряду і ходом $3$ з нижнього.

Вхідні дані

Кількість шестикутників $n (1 \leq n \leq 45)$ у верхньому ряді, у нижньому ряді їх кількість на $1$ менша.

Виведіть кількість способів дістатись з першої клітинки верхнього ряду до останньої клітинки цього ж ряду.

Вхідні дані #1

Відповідь #1

Вхідні дані #3

Відповідь #3

Відправки 6K

Коефіцієнт прийняття 47%