Dynamic Programming - Linear
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.
The length n (n ≤ 64) of the sequence.
Print the number of such sequences.