美麗的和是由若干個連續正整數相加所得的和。例如，$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