The Fibonacci number can be calculated as:

\[F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-1) + F(n-2), & \text{if } n \ge 2 \end{cases}\]

Given a positive integer \(N\) \((1 \le N \le 10^4)\), calculate the \(N^{th}\) Fibonacci number. Since the output can get very large, output the answer modulo by \(10^9 + 7\).

Input Specification

The first line of the input will contain one integer \(N\).

Output Specification

Output an integer, representing the \(N^{th}\) Fibonacci number modulo by \(10^9 + 7\).

Sample Input

4

Sample Output

3

Sample Explanation

The Fibonacci sequence is defined as

\[0, 1, 1, 2, 3, 5, 8, 13, \dots\]

The fourth term (0-indexed) in the sequence is \(3\).