Fast Fibonacci via Matrix Exponentiation

Given a non-negative integer n, compute the n-th Fibonacci number using the matrix exponentiation method. The Fibonacci sequence is defined as follows:

\(F(0)=0,\quad F(1)=1,\quad F(n)=F(n-1)+F(n-2) \text{ for } n \ge 2\).

It can be shown that if we define the matrix \[ A=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}, \] then \[ F(n)=\left(A^{n-1}\right)_{0,0}. \]

Your task is to implement an efficient algorithm that calculates F(n) using matrix exponentiation, ensuring that it works for large values of n (e.g., up to 1000).

inputFormat

The input is provided via standard input (stdin) and consists of a single non-negative integer n.

outputFormat

Output the n-th Fibonacci number to standard output (stdout) without any extra characters.## sample

0

0