Katta Fibonachchi

Qiyin 1 s 256 MB0 kishi yechgan

Fibonachchi sonlari: $F_0 = 0$ , $F_1 = 1$ , $F_k = F_{k-1} + F_{k-2}$ .

$F_n \bmod (10^9 + 7)$ ni toping.

Kiritish

Bitta butun son $n$ ( $0 \le n \le 10^{18}$ ).

$F_n$ ning $10^9 + 7$ ga bo‘lgandagi qoldig‘i.

Kiritish 1

Chiqarish 1

Kiritish 2

Chiqarish 2

$n$ juda katta: oddiy sikl ishlamaydi. Matritsani tez darajaga ko‘tarish yoki “fast doubling” usulidan foydalaning.

Manba: NolbirKod namuna