406975: GYM102644 C Fibonacci
Memory Limit:256 MB
Time Limit:0 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
C. Fibonaccitime limit per test0.25 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Find the $$$n$$$-th Fibonacci number modulo $$$10^9+7$$$.
So, you need to find $$$F_n$$$ in the sequence defined as $$$F_0 = 0$$$, $$$F_1 = 1$$$ and $$$F_i = F_{i-1} + F_{i-2}$$$ for $$$i \geq 2$$$.
InputAn integer $$$n$$$ ($$$0 \leq n \leq 10^{18}$$$).
OutputPrint the answer modulo $$$1000000007$$$.
ExamplesInput3Output
2Input
6Output
8Input
50Output
586268941Note
The first few terms of Fibonacci sequence are $$$(0, 1, 1, 2, 3, 5, 8, 13, \ldots)$$$. In particular, we have $$$F_0 = 0$$$, $$$F_3 = 2$$$ and $$$F_6 = 8$$$. And for the last sample test:
$$$$$$F_{50} = 12586269025 \equiv 586268941 \pmod {10^9 + 7}$$$$$$