150. Три единицы подряд

По данному числу $N$ определите количество последовательностей из нулей и единиц длины $N$, в которых никакие три единицы не стоят рядом.

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

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит $2^{31}-1$.