\(1 \times N\)의 격자판이 있다. 이 격자판을 \(1 \times 1\), \(1 \times 2\), \(1 \times 3\)의 타일을 이용하여 채울 수 있는 서로 다른 경우의 수를 구해보자.
계산한 결과를 1,000,000,007로 나눈 나머지를 출력한다.

정수 \(N\)이 입력된다.
\(1 \le N \le 1000000\)

서로 다른 경우의 수의 개수를 출력한다.