Feeding Duksu

Interview

Time limit1sMemory limit512 MB

Summary

Count the length-N sequences over four restaurants plus a skip state where you never revisit today's restaurant or its neighbors tomorrow, and a skip forces eating the next day.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

Duksu is busy with a project and has little time to eat. He usually eats once a day at one of the four restaurants he frequents. When he cannot be bothered, he skips the meal.

Duksu always wants a fresh experience, so he picks the restaurant for the next day by these rules.

On the first day, he either skips the meal or picks any one restaurant he wants.
If he did not skip yesterday, he may skip today.
If he skipped yesterday, he must go to a restaurant and eat today.
He does not go to the restaurant he went to today on the next day.
He does not go to a restaurant adjacent to the one he went to today on the next day.

If he went to restaurant 2 today, then tomorrow he does not go to restaurants $1$ , $2$ , $3$ . To get a fresh experience, he must either go to restaurant $4$ or skip the meal.

Duksu wants to make a meal plan for $N$ days. Write a program that counts the number of possible meal plans that follow the rules above.

Input

The first line gives $N$ , the total number of days in the lunch plan Duksu must make. $(1 \le N \le 200\,000)$

Output

Print the number of possible meal plans for $N$ days, modulo $1\,000\,000\,007(=10^9+7)$ .

Examples2

Example 1
Input
```
1
```
Expected output
```
5
```
Example 2
Input
```
2
```
Expected output
```
14
```