Fibonacci Sum

Given a positive integer (n), compute the sum of the first (n) Fibonacci numbers modulo (10^9+7). The Fibonacci sequence is defined as (F(1)=1), (F(2)=1) and (F(n)=F(n-1)+F(n-2)) for (n \ge 3). It can be proven that (\sum_{i=1}^{n}F(i) = F(n+2)-1). To efficiently compute (F(n+2)) for large (n), use matrix exponentiation.

Input is provided via standard input and output should be printed to standard output.

inputFormat

A single integer (n) ((1 \le n \le 10^9)). The input is read from standard input.

outputFormat

Output a single integer, the sum of the first (n) Fibonacci numbers modulo (10^9+7), printed to standard output.## sample

1

1