6-Laboratoriya ishi Mavzu: Dinamik programmalash

Dinamika va o’tish matritsasi.
Masalan Fibonatchi ketma-ketligini dinamik programmalash metodi bilan yechishga urinib ko’raylik. F[i]=F[i-2]+F[i-1] formula bizga ma’lum.
Endi (F[i], F[i-1]) ikkita sondan iborat vektorni va (F[i-1], F[i-2]) vektorni olaylik. (F[i], F[i-1]) ni (F[i-1]+F[i-2], F[i-1]) bilan almashtirishimiz mumkin. Uni esa (F[i-1], F[i-2]) vektorga quyidagicha bog’lash mumkin:
(F[i-1]+F[i-2], F[i-1]) = (F[i-1], F[i-2]) x
Bu asosiy formula hisoblanadi. Bizda esa F[1]=F[2]=1 ekanligi ma’lum. U holda quyidagilarni yozishimiz mumkin:
(F[3], F[2]) = (F[2], F[1]) x ;
(F[4], F[3]) = (F[3], F[2]) x = (F[2], F[1]) x x = (F[2], F[1]) x ;


(F[5], F[4]) = (F[4], F[3]) x = (F[2], F[1]) x x = (F[2], F[1]) x ;


Umumiy holda:
(F[n], F[n-1]) = (F[2], F[1]) x ;
Asosiy hisoblanishi kerak bo’lgan qiymat bu matritsaning (n-3) darajasini hisoblash. Buni esa binar darajaga ko’tarish algoritmi bo’yicha hisoblash mumkin.
Javob esa darajaga ko’tarilgan matritsaning (1, 1) va (2, 1) kataklarda turgan elementlarining yig’indisi.

Umumiy topshiriq
236. Fibonatchi ketma-ketligi
Vaqt limiti: 1 sekund 
Xotira limiti: 64 MB
Fibonatchi ketma-ketligi quyidagicha aniqlanadi. F₀=F₁=1, F_i=F_i-2+F_i-1(i > 1).
Sizning vazifangiz n-fibonatchi sonini topuvchi dastur tuzish.
Bu son juda katta bo’lishi mumkin, shuning uchun sizdan faqat uni 1000000007 (10⁹+7) ga bo’lgandagi qoldiqni topish so’raladi.
Kiruvchi ma’lumotlar: Birinchi qatorda bitta butun n soni berilgan. (0≤n≤10⁶).
Chiquvchi ma’lumotlar: Birinchi qatorda bitta sonni−masalaning javobini chiqaring.