Masala #1066

Zakovat klubida bugun g'alati quiz bo'lib o'tmoqda. Quizda jami n ta savol o'ynaladi. Har bir to'g'ri javob uchun 1 ball beriladi. Hamda o'yinda ketma-ket jami nechta savolga javob berganligi ham hisoblab boriladi. Har safar to'g'ri javob berilganda ushbu qiymat 1 ga oshiriladi. Agar noto'g'ri javob berilsa qiymat nolga aylantiriladi. Agar ketma-ket to'g'ri javoblar soni k ta bo'lsa ballar 2 karra ortadi va ketma-ket to'g'ri javoblar soni yana noldan hisoblana boshlaydi. Eslatma: bunda dastlab 1 ball qo'shiladi va keyin ball 2 karra ortiriladi. O'yin boshida ishtirokchining bali hamda ketma-ket to'g'ri javoblar soni nolga teng bo'ladi.

Ushbu quizda qatnashgan Mardon jami m ta savolga to'g'ri javob berganligini aytayapti ammo necha ball  olganligi yodida yo'q.

U olishi mumkin bo'lgan minimal balni 1000000009 ga bo'lgandagi qoldiqni topishda Mardonga yordam bering.

Kirish faylida 3 ta butun n, m, k sonlari bo'sh joy bilan ajratilgan holda kiritiladi. \(2 \le k \le n \le 10^9\) va  \(0 \le m \le n\)

Chiqish faylida Mardon olishi mumkin bo'lgan eng kichik ballning qiymatini 1000000009 ga bo'lgandagi qoldiqni chop eting.