시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB104147636546.795%

문제

하와와와... 대학생 라가는 '하와와'라는 말을 좋아하는 거시와요. 언제나 말 끝마다 '하와와'라고 말하는 라가는 자신이 좋아하는 하와와와 발음이 비슷한 하와이로 여행을 떠나기로 결심한 거시와요! 하와와와와... 그래서 라가는 구글 지도를 보면서 하와이 여행 계획을 세우고 있사와요...

하와이는 열도기 때문에, 라가는 열도들을 따라가면서 모든 섬을 여행하는 거시와요... 하와와와... 열도는 열을 따라 생겨 있는 섬이라는 뜻이고, 우리는 편의상 하와이의 섬 n개가 일렬로 배치되어 있다고 하는 거시와요... 이 때 첫 번째 섬에서 여행을 시작해야 하고, 열도를 여행하는 방법은 다음과 같이 세가지가 있는 거시와요...

  1. 어떤 섬을 보고 바로 그 다음 섬으로 갈 수 있사와요...
  2. 어떤 섬을 보고 한 섬을 건너뛰고 그 다음 섬으로 갈 수도 있사와요...
  3. 어떤 섬을 보고 그 이전 섬으로 갈 수 있사와요...

하와와.. 라가는 하와이의 모든 n개의 섬을 보고 싶은 거시와요... 또한, 라가는 지루함을 많이 타기 때문에 한번 갔던 섬에 다시 가고 싶지 않은 거시와요... 이 때, n개의 섬들이 있을 때 라가가 하와이를 여행하는 방법이 모두 몇 가지인지 구해 보는 거시와요...

하와와와... 그런데 저는 라가도 아닌데 왜 이런 말투를 쓰냐고요? 하와와 라가 친구쨩도 말투가 옮은 거시와요...

입력

첫째 줄에 하와이 열도의 섬의 개수 n(1 ≤ n ≤ 50,000)이 주어지는 거시와요 하와와. 하와와! 답이 커질 수 있으니 1,000,000,009로 나눈 나머지를 출력해 주시는 거시와요!

출력

첫째 줄에 라가가 여행할 수 있는 방법의 수를 출력하는 거시와요 하와와

예제 입력 1

2

예제 출력 1

1

예제 입력 2

5

예제 출력 2

4

첫번째 경우에는 섬이 두 개 있으니까 한 섬을 보고 바로 다음 섬으로 넘어가는 경우만 있는 거시와요

두번째 경우에는 바로 다음 섬을 가는 경우를 1, 한 섬 건너 한 섬으로 가는 것을 2, 그 전 섬으로 가는 것을 -1이라고 하면

1 1 1 1

1 2 -1 2

1 1 2 -1

2 -1 2 1의 4가지 경우가 있사와요...

 

출처