Tiling a 2 by N wall

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.

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

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