Nth Fibonacci Number Modulo 10^9+7

You are given a positive integer n. Your task is to compute the n-th Fibonacci number modulo \(10^9+7\). The Fibonacci sequence is defined as:

[ F(1)=1, \quad F(2)=1, \quad F(n)=F(n-1)+F(n-2) \text{ for } n\geq 3, ]

Due to the large size of n, a direct iterative or recursive approach will be too slow. You are required to use an efficient algorithm such as matrix exponentiation to compute the result in \(O(\log n)\) time.

Input Format: The input contains a single positive integer \(n\).

Output Format: Output the n-th Fibonacci number modulo \(10^9+7\) to standard output.

inputFormat

The input consists of a single line with one integer n (\(1 \leq n \leq 10^{9}\)).

outputFormat

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

## sample

5

5

</p>