Problem C. Cell painting

Author:Anton Karabanov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  


Timofey was painting the margins of his notebook during a boring class. In the first line he painted one cell, two in the second, and in the following lines one less or one more then the previous line. At the end of the class it turned out that he painted exactly n cells. How many ways was there for him to do that? The margins are narrow, so Timofey never painted more than three cells in a single line.

Input format

The single line of input contains a positive integer n — number of painted cells.

Output format

Output a single nonnegative integer — the number of different ways to paint. It's guaranteed to be no more than 1018.


1 ≤ n ≤ 200

Notes on the sample

See picture below.

Sample tests

No. Standard input Standard output

0.245s 0.041s 15