타일 채우기 3

$2 \times N$ 크기의 벽이 있다. 이 벽을 $2 \times 1$, $1 \times 2$, $1 \times 1$ 크기의 타일로 빈틈없이 채우려고 한다. 타일은 서로 겹칠 수 없고, 벽 밖으로 나갈 수 없으며, 각 크기의 타일을 몇 개든 쓸 수 있다.

벽을 채우는 방법의 수를 구하시오. 한 칸이라도 덮는 타일이 다르면 서로 다른 방법으로 센다.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 1{,}000{,}000$)

첫째 줄에 벽을 채우는 방법의 수를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.