Matrix Exponentiation - Fibonacci

View as PDF
Submit solution
Points: 0.40
Time limit: 0.25s
Memory limit: 256M
Input: stdin
Output: stdout
Suggester:
toha
Problem source:
Matrix Exponentiation
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãy tìm phần dư của phép chia lấy dư số Fibonacci thứ ~n~ cho ~10^9+7~.

Số Fibonacci thứ ~n~ ~(F_n)~ được xác định bởi dãy truy hồi sau:

~F_0 = 0, F_1 = 1~

~F_n = F_{n-1} + F_{n-2}\ (\forall n \geq 2)~

Input

Gồm ~1~ dòng chứa số nguyên ~n~ ~(0 \leq n \leq 10^{18})~.

Output

Phần dư của phép chia ~F_n~ cho ~10^9 + 7~.

Sample 1

Input
3
Output
2

Sample 2

Input
6
Output
8

Sample 3

Input
50
Output
586268941

~F_{50} = 12586269025 \equiv 586268941~ ~(mod ~ ~10^9 + 7)~.

Note

Một vài số hạng đầu tiên của dãy số Fibonacci là ~(0,1,1,2,3,5,8,13,…)~.

Comments

Please read the guidelines before commenting.


  • -16
    chunguyen2k8  commented on April 1, 2024, 12:25 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -31
    nogo007akapkn  commented on March 3, 2024, 4:51 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.