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.
The length (n \leq 64) of the sequence.
Print the number of such sequences.
Example 1
Example 2
Example 3