402048: GYM100633 F Beautiful sums

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Beautiful sumstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

Single line contains an integer n (1 ≤ n ≤ 105).

Output

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

ExamplesInput
3
Output
9
Input
4
Output
15

加入题单

上一题 下一题 算法标签: