아름다운 합

아름다운 합은 연속된 양의 정수 여러 개의 합이다. 예를 들어 $7 + 8$과 $4 + 5 + 6$은 아름다운 합이다. 하지만 $3 + 5 + 7$은 값이 모두 $15$로 같아도 아름다운 합이 아니다. (정수 하나만으로 이루어진 합, 예를 들어 $15$ 자체도 아름다운 합으로 본다.)

정수의 아름다움 지수는 그 정수를 아름다운 합으로 나타내는 방법의 수이다. 예를 들어 15는 $15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5$의 네 가지 방법으로 나타낼 수 있으므로 아름다움 지수가 4이다. 15는 아름다움 지수가 4인 가장 작은 정수이다.

아름다움 지수가 높은 정수일수록 더 아름답다. 지수가 같으면 더 작은 정수가 더 아름답다. 주어진 아름다움 지수 $n$에 대해, 지수가 $n$인 가장 작은 정수를 구하라.

첫째 줄에 정수 $n$ ($1 \le n \le 10^5$)이 주어진다.

아름다움 지수가 $n$인 가장 작은 정수를 $10^9+9$로 나눈 나머지를 출력한다.