Implement Fibonacci with efficiency constraints

Implement fib(n) for the 0-indexed Fibonacci sequence, where $$F(0)=0$$ and $$F(1)=1$$. For any $$i \ge 2$$, define $$F(i)=F(i-1)+F(i-2)$$. Because exact Fibonacci values become extremely large, return $$F(n) \bmod 1{,}000{,}000{,}007$$ instead of the full integer. The result must satisfy $$0 \le result < 1{,}000{,}000{,}007$$. Your implementation must support very large indices. A naive exponential recursive implementation is not acceptable; the expected time complexity is…