~/algor $ cat masalalar/zinapoya
DP-01
Zinapoya
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
64 MB
45%
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 mumkinligini aniqlang. Qadamlar ketma-ketligi farq qilsa, usullar har xil hisoblanadi.
Kiruvchi ma'lumotlar
Bitta natural son $n$.
Chiquvchi ma'lumotlar
Bitta butun son — usullar sonining $10^{9} + 7$ ga bo'lgandagi qoldig'i.
Izoh
$1 \le n \le 10^{6}$
Misollar
Kirish #1
3
Chiqish #1
4
Kirish #2
4
Chiqish #2
7