e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dynamic Programming - Linear

Simple task for Sharik

prb1281 Long before Sharik found a clever book, lost Pechkin when he first began his experiments on sawing chess boards, even when on the chessboard white fields were white, and black - the black, he asked one of his first Matroskin brainteasers.

"_How many different sequences of length n can be formed from cells of sawn chessboards, if none of the sequences of any three white field should not go straight._"

Matroskin have not decided yet this puzzle, so your task is to help him.

Input

The length n (n64) of the sequence.

Output

Print the number of such sequences.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
1
Output example #1
2
Input example #2
2
Output example #2
4
Input example #3
3
Output example #3
7