Tiles
Wayne has recently just bought a house, and wants to tile the floor. The floor is a 2xn grid, and there are 1x1, 1x2 and 2x2 tiles available. How many ways are there to tile the floor?
Input
The input will contain an integer n
Output
Output the answer mod 10^9+7
Subtasks
subtask 1 (0%): Sample
subtask 2 (5%): n<=1000
subtask 3 (10%): n<=2000000
subtask 4 (85%): n<=10^16
Sample input
2
Sample output
8
Explaination
There are 8 ways
_ _ _ _ _ _ _ _
|_|_| |_| | | |_| |_ _|
|_|_| |_|_| |_|_| |_|_|
_ _ _ _ _ _ _ _
|_|_| | | | |_ _| | |
|_ _| |_|_| |_ _| |_ _|