Problems
Simple task for Sharik
Simple task for Sharik
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 data
The length n (n ≤ 64) of the sequence.
Output data
Print the number of such sequences.
Examples
Input example #1
1
Output example #1
2
Input example #2
2
Output example #2
4
Input example #3
3
Output example #3
7