Efficient Fibonacci Computation

Given a non-negative integer (n), compute the (n)th Fibonacci number modulo (10^9+7). The Fibonacci sequence is defined as follows: (F(0)=0, F(1)=1) and (F(n)=F(n-1)+F(n-2)) for (n \ge 2). In this problem, you are required to utilize the technique of matrix exponentiation to efficiently calculate the answer even for very large values of (n).

inputFormat

Input consists of a single line containing a non-negative integer (n) ((0 \le n \le 10^{18})).

outputFormat

Output a single integer which is the (n)th Fibonacci number modulo (10^9+7).## sample

0

0