Fibonacci of a Huge Index

The Fibonacci numbers start F(0) = 0 and F(1) = 1, and each one after that is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, ...

Write fib_mod(n) that returns F(n) modulo 1,000,000,007, that is F(n) % 1_000_000_007.

Examples

fib_mod(10)    # returns 55
fib_mod(0)     # returns 0
fib_mod(50)    # returns 586268941

F(50) is 12,586,269,025, and 12,586,269,025 % 1,000,000,007 is 586,268,941.

Constraints

• 0 <= n <= 10^18
• A loop that walks along the sequence one number at a time would need a billion billion steps for the largest n.