Write a program that prints the number of sequences of length *n*
made up of only zeros and ones
that do not contain two consecutive zeros nor three consecutive ones.

For instance, there are 7 sequences for *n* = 5:

01010 01011 01101 10101 10110 11010 11011 |

**Input**

Input consists of several natural numbers *n*,
each between 0 and 150.

**Output**

For every *n*, print the required number.

Public test cases

**Input**

0 1 2 3 5 150

**Output**

1 2 3 4 7 3495391431926239764

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Python