목공소 장인은 \(2 \times N\) 크기의 바닥을 타일로 빈틈없이, 겹치지 않게 채우려 한다. 사용할 수 있는 타일은 다음 세 종류이다.

• \(1 \times 2\) 세로 타일 (한 칸 폭에 세로로 꽉 차는 타일)
• \(2 \times 1\) 가로 타일 (가로로 두 칸 차지, 위/아래 칸 각각에 놓을 수 있음)
• \(2 \times 2\) 정사각 타일

바닥을 채우는 서로 다른 방법의 수를 구하여라. 값이 클 수 있으므로 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력한다.

• \(1 \le N \le 1{,}000{,}000\)

첫째 줄에 정수 \(N\) 이 주어진다.

\(2 \times N\) 바닥을 채우는 방법의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original