Tiling a 2 by N wall

Time limit2sMemory limit512 MB

Summary

Count the ways to tile a 2 by N wall with 2x1, 1x2, and 1x1 tiles, modulo 1e9+7.

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

Problem

You are given a wall of size $2 \times N$ . Fill the wall completely with tiles of size $2 \times 1$ , $1 \times 2$ and $1 \times 1$ . Tiles must not overlap, no tile may stick out of the wall, and each size may be used any number of times.

Count the ways to fill the wall. Two ways are different when some cell is covered by a different tile.

Input

The first line contains an integer $N$ . ( $1 \le N \le 1{,}000{,}000$ )

Output

Print the number of ways to fill the wall, taken modulo $1{,}000{,}000{,}007$ , on the first line.

Examples3

Example 1
Input
```
1
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
7
```
Example 3
Input
```
3
```
Expected output
```
22
```