Masala #CH4RZWU3G0
Teleportatsiya
Nyuboy xayolida “Teleport” nomli o'yinni o'ynayapti. O'yin n ta bosqichdan iborat. Nyuboyning vazifasi n-bosqichga yetib borish. Nyuboyning o'yindagi teleportatsiya kuchi k ga teng, ya'ni u hozir i-bosqichda bo'lsa bitta harakatda keyingi k ta bosqichdan biriga teleportatsiya qila oladi. Nyuboyning n-bosqichga yetib borish variantlar sonini chop eting.
Nyuboy o'yinni 1-bosqichda boshlaydi.
Yagona qatorda n va k natural sonlari mos ravishda o'yindagi bosqichlar soni va Nyuboyning xayoliy teleportatsiya kuchi kiritiladi.
\((n \le 10^{15}, k \le min(n, 100))\)
Nyuboyning n-bosqichga yetib borish variantlar sonini \(10^9 + 7\) ga bo'lgandagi qoldig'ini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 2 |
3 |
1-namunaviy testda
1 → 2 → 3 → 4
1 → 2 → 4
1 → 3 → 4
Xuddi shunday 3 xil usulda yetib kelishi mumkin.
!!! Agar siz pythonda ishlasangiz yechimingizni pypy da jo'nating.
Telegram kanalimizga obuna bo'ling