AL09-1. Zinapoya

Zinapoyada n ta pog‘ona bor. Bir qadamda 1 yoki 2 pog‘ona ko‘tarilish mumkin. Tepaga necha xil usulda chiqish mumkin? Javob katta — uni 10⁹ + 7 ga bo‘lgandagi qoldiqni chiqaring.

n-pog‘onaga oxirgi qadam yo n − 1 dan, yo n − 2 dan keladi. Demak yo‘l(n) = yo‘l(n − 1) + yo‘l(n − 2), yo‘l(0) = yo‘l(1) = 1.

Kirish ma’lumotlari

Bitta butun son n.

Chiqish ma’lumotlari

Usullar soni 10⁹ + 7 ga bo‘lgandagi qoldiq.

Cheklovlar

1 ≤ n ≤ 10⁶