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

The length n (n ≤ 64) of the sequence.

Output

Print the number of such sequences.

Examples