Beautiful sums

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

요약

연속한 양의 정수의 합으로 나타내는 방법의 수가 n인 가장 작은 정수를 구해 10^9+9로 나눈 나머지를 출력한다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Beautiful sums are the sums of several consequent positive integers. For example, the sums $7 + 8$ and $4 + 5 + 6$ are beautiful, and the sum $3 + 5 + 7$ is not beautiful even though the value in all cases equals $15$ . (The sum of single summand $15$ also considered beautiful.)

Given this, the beauty index of integer is the number of its representations as a beautiful sum. For example, the beauty index of number 15 equals 4 as 15 is represented by a beautiful sum in four ways: $15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5$ .

One number is more beautiful than another if its beauty index is higher. If numbers have equal beauty indexes the smaller one is considered more beautiful. For example, $15$ is the smallest integer having beauty index $4$ .

You have to find the smallest integer for given beauty index $n$ .

입력

Single line contains an integer $n$ ( $1 \le n \le 10^5$ ).

출력

Output the smallest integer for given beauty index $n$ modulo ( $10^9+9$ ).

예제2

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