Fibonacci Numbers by Matrix Exponentiation

This problem requires you to compute the nth Fibonacci number using matrix exponentiation. The Fibonacci sequence is defined as:

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

Using matrix exponentiation, the nth Fibonacci number can be derived from the relation:

\[ \begin{pmatrix}1 & 1\\1 & 0\end{pmatrix}^{n} = \begin{pmatrix}F(n+1) & F(n)\\ F(n) & F(n-1)\end{pmatrix} \]

Your task is to implement an efficient algorithm based on this method to compute \(F(n)\) even for very large values of \(n\). Input is given through standard input and output should be printed to standard output.

inputFormat

The input consists of a single line containing a non-negative integer \(n\) (where \(0 \le n\)) that represents the position in the Fibonacci sequence.

outputFormat

Output a single line containing the nth Fibonacci number.

0

0