靚嘅和係幾個連續正整數相加得出嘅和。例如，$7 + 8$ 同 $4 + 5 + 6$ 都係靚嘅和，而 $3 + 5 + 7$ 就唔係，雖然佢哋嘅值全部都等於 $15$。（只有一個加數 $15$ 嘅和亦算係靚嘅和。）
因此，一個整數嘅靚度指數，就係將佢表示成靚嘅和嘅方法數。例如，數字 $15$ 嘅靚度指數等於 $4$，因為 $15$ 可以用四種方法表示成靚嘅和：$15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5$。
如果一個數嘅靚度指數較高，就認為佢比另一個數更靚。如果兩個數嘅靚度指數相同，就認為較細嗰個數更靚。例如，$15$ 係靚度指數為 $4$ 嘅最細整數。
你要搵出靚度指數等於畀定嘅 $n$ 嘅最細整數。
輸入格式
唯一一行有一個整數 $n$（$1 \le n \le 10^5$）。
輸出格式
輸出靚度指數等於畀定嘅 $n$ 嘅最細整數對 $(10^9 + 9)$ 取模嘅結果。
例子
輸入格式 1
3
輸出格式 1
9
輸入格式 2
4
輸出格式 2
15