Matrix Exponentiation - Fibonacci

View as PDF

Submit solution


Points: 0.40
Time limit: 0.25s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
Matrix Exponentiation
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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.


There are no comments at the moment.