Fibonacci Modulo Computation

Given a non-negative integer n, compute the n-th Fibonacci number modulo \(10^9+7\). The Fibonacci sequence is defined as:

\(F(0)=0, F(1)=1\) and \(F(n)=F(n-1)+F(n-2)\) for \(n \geq 2\).

You are required to implement an efficient algorithm that computes \(F(n) \bmod (10^9+7)\) using matrix exponentiation. The transformation matrix for the Fibonacci sequence is given by:

\(\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}\)

Raising this matrix to the power of \(n-1\) yields a matrix whose top-left element is \(F(n)\) for \(n \geq 1\). For \(n=0\), output 0.

inputFormat

The input consists of a single line containing a non-negative integer n (0 \(\leq\) n \(\leq\) 10¹⁸).

outputFormat

Output the n-th Fibonacci number modulo \(10^9+7\) as an integer.

10

55