20544번 - 공룡게임

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

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

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

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

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

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

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

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

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