Simple Sequence Task#1281

Simple Sequence Task

1 second
128 megabytes
Very easy

Long before Donatello invented his famous bo staff, when he first began his experiments with patterns on sewer tiles, at a time when green tiles were green and orange tiles were orange, he gave his brother Leonardo one of his first puzzles.

"How many different sequences of length can be formed from tiles of sewer tunnels, if in any sequence, no three green tiles are consecutive?"

Leonardo has not yet solved this puzzle, so your task is to help him.

Input

The length (n \leq 64) of the sequence.

Output

Print the number of such sequences.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading