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
 _ _   _ _   _ _   _ _
|_|_| |_| | | |_| |_ _|
|_|_| |_|_| |_|_| |_|_|
 _ _   _ _   _ _   _ _
|_|_| | | | |_ _| |   |
|_ _| |_|_| |_ _| |_ _|