|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
Иван Иванович глубоко убеждён, что каждый день его жизни является либо счастливым, либо несчастливым. Более того, Иван Иванович привык вести календарь, в котором отмечает, каким оказался прошедший день. Если случается так, что три дня подряд были несчастливыми, то Иван Иванович приходит к выводу, что в жизни наступила чёрная полоса, и впадает в депрессию.
Впереди у Ивана Ивановича заслуженный отпуск, который продлится N дней. Иван Иванович задумался: сколько существует вариантов расположения счастливых и несчастливых дней в течение отпуска, не приводящих к депрессии? Помогите ему найти ответ на этот вопрос.
Входные данные
Входной поток содержит целое число N (1 <= N <= 31) — количество дней отпуска.
Выходные данные
Выведите единственное целое число — количество различных последовательностей из N дней, в которых нет трёх несчастливых дней подряд.
Примеры
| Входные данные | Выходные данные |
| 3 | 7 |
| 15 | 10609 |
Для отправки решений необходимо выполнить вход.
|