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