Nth Fibonacci Number

You are given a non-negative integer \(n\). Your task is to 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 \ge 2\).

For example:

• If \(n=5\), then \(F(5)=5\).
• If \(n=10\), then \(F(10)=55\).

Your solution should be efficient enough to handle very large values of \(n\) (up to about \(10^9\) or more).

inputFormat

The input is provided via standard input and consists of a single line containing one non-negative integer \(n\).

outputFormat

Output a single integer - the \(n\)th Fibonacci number modulo \(10^9+7\) printed to standard output.

0

0