e-olymp
Problems

Simple task for Sharik

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