Fibonacci Sequence Modulo

The Fibonacci sequence is defined as follows:

\( F_n = \begin{cases} 1, & n \le 2 \\ F_{n-1}+F_{n-2}, & n \ge 3 \end{cases} \)

Given an integer n, compute \( F_n \bmod (10^9+7) \). Note that the modulus is applied after the computation of \( F_n \).

inputFormat

The input consists of a single integer n (1 ≤ n).

outputFormat

Output the value of \( F_n \bmod (10^9+7) \) as a single integer.

sample

1

1