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