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