공기놀이

집에서 태준이와 공기놀이를 하던 홍준이는 태준이에게 다음과 같은 질문을 받았다.

“빨간 돌과 파란 돌이 각각 N개가 있어. 이것들을 일렬로 늘어놓되, 빨간 돌 하나와 파란 돌 하나를 택했을 때 빨간 돌이 파란 돌보다 왼쪽에 오는 경우의 수가 홀수 개가 되도록 하고 싶은데 이렇게 일렬로 늘어놓는 경우의 수가 얼마나 있을까?”

홍준이는 형의 질문을 듣고 오랫동안 고민하였지만 끝내 풀지 못하였다. 홍준이는 풀던 문제를 못 풀면 폭식을 하는 버릇이 있다. 홍준이가 폭식하지 않도록 문제를 풀어주자.

첫째 줄에는 하나의 양의 정수 N이 주어진다. (1 ≤ N ≤ 10,000,000)

첫째 줄에 태준이가 궁금해하는 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제의 경우, 돌들을 일렬로 늘어놓을 수 있는 경우의 수는 빨간 돌 – 파란 돌 / 파란 돌 – 빨간 돌, 2가지 경우이다. 이 중, 전자의 경우에만 빨간 돌이 파란 돌보다 왼쪽에 오는 경우의 수가 홀수가 되므로 답은 1가지가 된다.