#945. Фибоначчи mod 10⁹+7 (их n)
n өгөгдөнө (n ≤ 10¹⁸). Fₙ mod 1000000007-г ол (F₀ = 0, F₁ = 1). Зөвлөгөө: матриц эсвэл хурдан давхарлах арга.
### Оролт
Нэг бүхэл тоо n.
### Гаралт
Тоо.
Жишээ
Оролт
22363955353728191
Гаралт
384449992
Оролт
9292445420288466
Гаралт
334156964
💡 Python, JavaScript эсвэл блокоор бодож болно. Оролтыг input()-оор мөр мөрөөр нь уншина. Асуулт бичих хэрэггүй (жишээ нь input("Тоо: ")). Яг гаралтад заасан зүйлийг л хэвлэ.
🔒 Эхний 3 бодлогыг бүртгэлгүй бодож болно. Энэ бодлогыг бодохын тулд үнэгүй бүртгүүлээрэй!