Masala #DDB0BP0MVL

Xotira 16 MB Vaqt 1000 ms

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