ผลบวกที่สวยงามคือผลบวกของจำนวนเต็มบวกที่เรียงติดกันหลายจำนวน ตัวอย่างเช่น ผลบวก $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