하와와 대학생쨩 하와이로 가는 거시와요~
면접 대비시간 제한1초메모리 제한256 MB
1번 섬에서 출발해 +1, +2, -1 이동으로 각 섬을 정확히 한 번씩 모두 방문하는 경로의 수를 1,000,000,009로 나눈 나머지로 구합니다.
문제
하와와와... 대학생 라가는 '하와와'라는 말을 좋아하는 거시와요. 언제나 말끝마다 '하와와'라고 말하는 라가는 발음이 비슷한 하와이로 여행을 떠나기로 결심한 거시와요! 하와와와와... 그래서 라가는 구글 지도를 보면서 하와이 여행 계획을 세우고 있사와요...
하와이는 열도기 때문에, 라가는 열도를 따라가면서 모든 섬을 여행하는 거시와요... 하와와와... 열도는 열을 따라 생겨 있는 섬이라는 뜻이고, 우리는 편의상 하와이의 섬 n개가 일렬로 배치되어 있다고 하는 거시와요... 이때 첫 번째 섬에서 여행을 시작해야 하고, 열도를 여행하는 방법은 다음과 같이 세 가지가 있는 거시와요...
- 어떤 섬을 보고 바로 그 다음 섬으로 갈 수 있사와요...
- 어떤 섬을 보고 한 섬을 건너뛰고 그다음 섬으로 갈 수도 있사와요...
- 어떤 섬을 보고 그 이전 섬으로 갈 수 있사와요...
하와와.. 라가는 하와이의 모든 n개의 섬을 보고 싶은 거시와요... 또한, 라가는 지루함을 많이 타기 때문에 한 번 갔던 섬에 다시 가고 싶지 않은 거시와요... 이때, n개의 섬이 있을 때 라가가 하와이를 여행하는 방법이 모두 몇 가지인지 구해 보는 거시와요...
하와와와... 그런데 저는 라가도 아닌데 왜 이런 말투를 쓰냐고요? 하와와 라가 친구쨩도 말투가 옮은 거시와요...
입력
첫째 줄에 하와이 열도의 섬의 개수 n(1 ≤ n ≤ 50,000)이 주어지는 거시와요 하와와. 하와와! 답이 커질 수 있으니 1,000,000,009로 나눈 나머지를 출력해 주시는 거시와요!
출력
첫째 줄에 라가가 여행할 수 있는 방법의 수를 출력하는 거시와요 하와와