Some sequences of bits (1) P81826


Statement
 

pdf   zip

html

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++