סכומים יפים הם סכומים של כמה מספרים שלמים חיוביים עוקבים. למשל, הסכומים $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