Problem Statement

Pondo would like to know the ~n^{th}~ Fibonacci number modulo ~10^9+7~. The ~n^{th}~ Fibonacci number is determined by the following recurrence ~f(n) = f(n - 1) + f(n - 2)~ and ~f(1) = 1, f(0) = 0~.

Input Format

Your first line of input will contain a single integer ~n~.

Output Format

Output a single integer representing the ~n^{th}~ Fibonacci number modulo ~10^9+7~.

Constraints

• ~1 \leq n \leq 10^9~ ## Sample Cases ### Input 1

10

Output 1

55

Input 2

1000000000

Output 2

21

Explanation 2

Remember to modulo.

Input 3

99999999

Output 3

36891058