Masalalar
#025
~/algor $ cat masalalar/zinapoya
Zinapoya
O'rtacha
1000 ms
64 MB
30%
Mavzular:
Dinamik dasturlash
Zinapoya n ta pog'onadan iborat. Bir qadamda 1, 2 yoki 3 pog'ona yuqoriga chiqish mumkin. Pastdan (0-pog'onadan) aynan n-pog'onaga necha xil usulda chiqish mumkin?
Javob juda katta bo'lishi mumkin, shuning uchun uni 10⁹ + 7 ga bo'lgandagi qoldiqni chiqaring.
Kiruvchi ma'lumotlar
Bitta butun son n.
Chiquvchi ma'lumotlar
Bitta butun son — usullar soni, 10⁹ + 7 ga bo'lgandagi qoldiq.
Izoh
1 ≤ n ≤ 10⁶
Masalan, n = 3 bo'lsa: 1+1+1, 1+2, 2+1, 3 — jami 4 usul.
Misollar
Kirish #1
3
Chiqish #1
4
Kirish #2
4
Chiqish #2
7