Masala I

Fan olimpiadalari markazi (FOM) nihoyat "O'qituvchilar Olimpiadasi"ni o'tkazdi! Ustozlarimiz bilimda kuch sinashib, butun Respublika bo'ylab eng zo'r o'qituvchi nomiga loyiq bo'lishdi. Hamma ishtirokchilar natijalarini intiqlik bilan kutmoqda, sababi FOM barcha qatnashchilarga alohida pul mukofoti tayyorladi! Lekin, albatta, buni ham ajoyib va adolatli tarzda amalga oshirish rejalangan:

• FOM dagi pul kupyuralari faqat \(K^0, K^1, K^2, ..., K^{\infty}\) ko'rinishida (ya'ni, K ning nomanfiy butun darajalari).
• Ustozlar bir xil qiymatdagi kupyuradan ko'pi bilan bittadan olishi mumkin va har bir ustoz hech bo'lmaganda bitta kupyura bilan taqdirlanadi.
• Eng oxirgi oʻrindagi ustoz, yaʼni \(N\)-oʻrin egalari, yuqoridagi cheklovlar asosida to'lash mumkin bo'lgan eng kichik miqdordagi mukofotni oladi. \((N-1)\)-o'rin sohibi esa undan keyingi eng kichik mukofotni, va hokazo. \(i\)-o‘rindagi ustoz \(N-i+1\)-eng kichik mukofotga ega bo‘ladi, boshqacha so'zlar bilan aytganda, eng kichik mukofot — oxirgi o‘ringa, eng katta mukofot esa 1-o‘ringa beriladi..

Misol uchun, agar \(N = 5, K = 3\) bo‘lsa:

Eng kichik hosil qilib bo‘ladigan mukofotlar: \([1, 3, 4, 9, 10]\). Demak, 1-o‘rin uchun 10 so‘m, 2-o‘rin uchun 9 so‘m, va hokazo!

Endi har bir ustoz o'z o'rnini biladi va mukofot miqdorini ham bilishni xohlaydi. Ularning hayajonini kutarib, siz tashkilotchi sifatida qo'lga kiritgan mukofotlarni aniqlab, ularga xursandchilik ulashing!

Birinchi qatorda probel bilan ajratilgan 3 ta natural son \(N, K, Q \) - ishtirokchilar soni, FOM tomonidan belgilangan kupyura birligi, hamda so'rovlar soni kiritiladi.

Keyingi \(Q\) ta qatorning har birida 1 tadan butun son - o'qituvchi egallagan o'rin kiritiladi.

\(1 \le N \le 10^9\)

\(1 < K \le 10^9\)

\(1 \le Q \le 10^5\)

Har bir so'rov uchun alohida qatorda, o'qituvchi oladigan mukofot qiymatini chop eting. Javob juda katta bo‘lishi mumkin, shu sababli natijaning \(10^9 + 7\) ga bo‘lgandagi qoldig'ini chop eting.