Beautiful sums

Time limit1sMemory limit1024 MB

Summary

Given n, find the smallest integer with exactly n odd divisors (equivalently n beautiful sum representations), printed modulo 1000000009.

Level: Medium6 of 10
Topics: Number theory, Math, Backtracking
Solved: No attempts yet

Problem

Beautiful sums are sums of several consecutive positive integers. For example, the sums $7 + 8$ and $4 + 5 + 6$ are beautiful, but $3 + 5 + 7$ is not, even though all three equal $15$ . (A sum with a single summand, such as $15$ alone, is also considered beautiful.)

The beauty index of an integer is the number of ways it can be written as a beautiful sum. For example, 15 has beauty index 4 because $15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5$ , and 15 is the smallest integer with beauty index 4.

An integer with a higher beauty index is more beautiful. If two integers have the same beauty index, the smaller one is more beautiful. For a given beauty index $n$ , find the smallest integer with that beauty index.

Input

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

Output

Output the smallest integer with beauty index $n$ modulo $10^9+9$ .

Examples2

Example 1
Input
```
3
```
Expected output
```
9
```
Example 2
Input
```
4
```
Expected output
```
15
```