402048: GYM100633 F Beautiful sums

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 ≤ n ≤ 10⁵).

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

3

9

4

15