시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 131 67 58 63.043%

문제

리유나는 양팔저울을 가지고 놀고 있다. 무게가 $2^1$, $2^2$, $\cdots$, $2^N$인 $N$개의 추가 있고, 적당한 순서로 서로 다른 $N$개의 추를 하나씩 놓는 동안, 왼쪽의 무게가 오른쪽의 무게를 넘지 않도록 하고 싶다. 추를 놓는 순서의 경우의 수를 구하여라.

입력

첫째 줄에는, $N$이 주어진다. ($1 \le N \le 50000$)

출력

첫째 줄에, 추를 놓는 순서의 경우의 수를 구하여라. 단, 답이 매우 클 수 있으니, 1000000009 ($=10^9 + 9$) 로 나눈 나머지를 구하여라.

예제 입력

2

예제 출력

3

예제 입력 2

3

예제 출력 2

15

힌트