Masala #DDB0BP0MVL
Xotira 16 MB
Vaqt 1000 ms
14
Zinapoyalar
N zinapoyali zinapoya bor. Siz esa eng tepada turipsiz. Har bir harakat bilan bir vaqtning o'zida 1, 2 yoki 3 zina pastga tushishni tanlashingiz mumkin. Bu zinadan necha xil yo‘l bilan tushishingiz mumkin?
Kiruvchi ma'lumotlar:
Bitta butun N (1 ≤ N ≤ 1 000 000), zinapoyadagi zinapoyalar soni.
Chiquvchi ma'lumotlar:
Bitta butun son, zinapoyadan pastga tushadigan turli xil raqamlar kombinatsiyasi. Javob biroz katta bo'lishi mumkin, shuning uchun javobni bizga tanish bo'lgan 1000000007 ga bo'lgandagi qoldiqni toping.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
1 |
1 |
| 2 |
5 |
13 |
| 3 |
1000000 |
746580045 |
Telegram kanalimizga obuna bo'ling