Три одиниці підряд

Дуже проста

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

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

За заданим числом N визгачте кількість послідовностей з нулів та одиниць довжни N, у яких ніякі три одиниці не стоять поряд.

Вхідні дані

У вхідному файлі написано натуральне число N, яке не перевищує 35.

Виведіть кількість шуканих послідовностей. Гарантується, що відповідь не перевищує 2^31-1.

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

Відповідь #1

Відправки 1K

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