양팔저울

시간 제한1초메모리 제한256 MB

요약

무게 2^1부터 2^N까지의 추를 순서대로 하나씩 접시에 올리면서 왼쪽 접시가 오른쪽 접시를 넘지 않도록 놓는 경우의 수를 10^9+9로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 조합론, 동적 계획법, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

리유나는 양팔저울로 놀고 있다. 무게가 $2^1$ , $2^2$ , $\cdots$ , $2^N$ 인 추가 하나씩, 모두 $N$ 개 있다. 리유나는 아직 올리지 않은 추를 하나 골라 저울의 왼쪽 접시나 오른쪽 접시에 올리고, $N$ 개를 모두 올릴 때까지 이 과정을 반복한다. 추를 하나 올릴 때마다 왼쪽 접시에 올라간 무게의 합이 오른쪽 접시에 올라간 무게의 합을 넘지 않아야 한다.

이렇게 추를 올리는 방법이 몇 가지인지 구하여라. 추를 올린 순서가 같고 각 추를 올린 접시도 같을 때만 두 방법을 같은 방법으로 센다.

입력

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

출력

첫째 줄에 추를 올리는 방법의 수를 $1000000009$ ( $=10^9 + 9$ )로 나눈 나머지를 출력한다.

예제3

예제 1
입력
```
1
```
예상 출력
```
1
```
예제 2
입력
```
2
```
예상 출력
```
3
```
예제 3
입력
```
3
```
예상 출력
```
15
```