Определите количество последовательностей из нулей и единиц длины N (длина - это общее количество нулей и едииниц), в которых никакие три единицы не стоят рядом.
Входные данные
Вводится натуральное число N, не превосходящее 40.
Выходные данные
Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2
31 − 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
7
|