Fibonacci, Astronomically
Print F(N) mod 109+7 where F(0)=0, F(1)=1 — and N is up to 1018, so linear iteration is hopeless.
Input: one integer N.
Output: F(N) mod 109+7.
Constraints:
- 0 ≤ N ≤ 1018
Sample Tests
Input 1
10
Output 1
55
Input 2
0
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.