공룡게임

시험을 맞아 하이테크관에서 급하게 벼락치기를 하던 도현이는 오늘도 인터넷 연결 없음 창을 마주하게 되었다!

위 창에서 스페이스바를 누르면 공룡게임을 플레이할 수 있다. 공룡게임의 규칙을 설명하자면 공룡은 계속해서 앞으로 전진한다. 맵에 무작위로 장애물인 선인장이 등장하는데, 적절한 타이밍에 스페이스바를 누르면 점프를 해서 선인장을 뛰어넘을 수 있다. 점프를 적절한 타이밍에 누르지 못하면 공룡이 선인장에 부딪히게 되어 게임이 종료된다. 이때 게임 시간에 비례한 점수를 얻는다. 의욕이 팍 떨어져 버린 도현이는 그대로 스페이스바를 눌러 공룡게임을 플레이하였지만, 수많은 문제 풀이로 다져진 그의 피지컬 앞에선 게임이 너무 쉬워서 도저히 게임이 끝나지를 않았다! 원래의 공룡게임은 점프를 잘하면 이론상 무한히 플레이할 수 있기 때문에, 무료해진 도현이는 아래와 같이 규칙을 바꾼 후 자신이 깰 수 있는 맵의 가짓수를 세보기로 했다.

• 맵의 길이는 N으로 주어진다. 이 맵은 N개의 지점으로 이루어지며, 각 지점은 바닥이나 높이가 1 또는 2인 선인장(장애물)으로 이루어진다. 시작 지점은 1이며, 공룡이 앞으로 갈수록 지점을 나타내는 수가 증가한다.
• 공룡은 최대 2개의 인접한 선인장을 뛰어넘을 수 있으며, 인접한 두 선인장의 높이의 합이 4 이상이면 뛰어넘을 수 없다.
• 시작부터 장애물을 밟으면 살아남을 수 없기 때문에 시작 지점은 무조건 바닥이다.
• 맵에 높이가 2인 선인장이 하나도 등장하지 않으면 너무 지루하다. 따라서 높이가 2인 선인장이 적어도 하나는 등장해야 한다.
• 위 조건을 전부 만족하면서 선인장에 부딪히지 않고 상태가 바닥으로 고정된 가상의 N+1번째 지점으로 도착하면 깰 수 있다고 정의한다.
• 인접한 선인장이 존재하면 반드시 한 번에 뛰어넘어야 한다.

깰 수 없는 맵의 한 예시. 지점 2, 3에 높이가 2인 선인장이 연속해서 등장하기 때문에 공룡은 선인장에 부딪히게 된다.

깰 수 있는 맵의 가짓수를 구해서 도현이의 무료함을 달래주자.

맵의 길이 $N$ (1 ≤ $N$ ≤ 1000)이 주어진다.

위 조건을 모두 만족하면서 도현이가 깰 수 있는 맵의 가짓수를 출력한다.

수가 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

크롬 브라우저에서 인터넷 연결이 안 될 때나 주소창에 chrome://dino를 입력하면 공룡게임을 플레이할 수 있다.