1, 2, … , n 의 순열 A1, A2, … An 이 A1 < A2 > A3 < A4 > A5 < A6 … 을 만족할 때 {An}를 진동 순열이라 한다. n 이 주어질 때 진동순열의 개수를 1,000,000,009로 나눈 나머지를 구하시오.

입력

출력

입출력 예

입력

4

출력

5

입출력 예 보충:

출처:ainta