Competitions

# 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.

#### Input

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

#### Output

Print the number of such sequences.

Input example #1

1

Output example #1

2

Input example #2

2

Output example #2

4

Input example #3

3

Output example #3

7