eolymp
bolt
Try our new interface for solving problems
Problems

Simple task for Sharik

Simple task for Sharik

Time limit 1 second
Memory limit 128 MiB
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 data

The length n (n64) 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