A. Асуултын хариултын тоглоом

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Манао асуулт хариултын тоглоомоор тоглож байлаа. Тоглоом нийтдээ $n$ асуулттай ба асуултуудад нэг нэгээр нь хариулна. Зөв хариулбал нэг оноо нэмж авах ба дарааллан зөв хариулсныг тоолдог тоолуур бас байгаа.

Хэрвээ зөв хариулбал дараалсан онооны тоолуур $1$-ээр нэмэгдэнэ. Хэрвээ буруу хариулбал энэ тоолуур тэглэгдэнэ. Тоолуур нэмэгдсээр байгаад $k$ хүрвэл тоолуур тэглэгдэх ба зөв хариулсан нэг оноо нь нэмэгдсэний дараа байгаа оноо нь хоёроор үржигдэнэ.

Тоглоомын эхэнд тоглогчийн оноо ба дараалсан онооны тоолуур адилхан $0$ байна.

Манао яг $m$ асуултанд зөв хариулснаа мэдэж байгаа боловч дарааллыг нь санахгүй байлаа. Тэр өөрийнхөө авч болох хамгийн бага оноог мэдэхийг хүсэв. Түүнд энэ оноог нь $1000000009$-д ($10^9+9$) үлдэгдэлтэй хуваасан тоог тооцоолж олж өгнө үү.

Оролт

Нэг мөрөнд зайгаар тусгаарлагдсан $n$, $m$, $k$ тоонууд ($2 ≤ k ≤ n ≤ 10^9$; $0 ≤ m ≤ n$).

Гаралт

Манаогийн авч болох хамгийн бага оноог $1000000009$-д ($10^9+9$) хуваасан үлдэгдэл.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
5 3 2
Гаралт
3
Оролт
5 4 2
Гаралт
6

Тэмдэглэл

Sample 1. Manao answered 3 questions out of 5, and his score would double for each two consecutive correct answers. If Manao had answered the first, third and fifth questions, he would have scored as much as 3 points.

Sample 2. Now Manao answered 4 questions. The minimum possible score is obtained when the only wrong answer is to the question 4.

Also note that you are asked to minimize the score and not the remainder of the score modulo $1000000009$. For example, if Manao could obtain either $2000000000$ or $2000000020$ points, the answer is $2000000000 mod 1000000009$, even though $2000000020 mod 1000000009$ is a smaller number.

Сэтгэгдлүүдийг ачааллаж байна...