CSES - Fibonacci Numbers
  • Time limit: 1.00 s
  • Memory limit: 512 MB

The Fibonacci numbers can be defined as follows:

  • F_0=0
  • F_1=1
  • F_n = F_{n-2}+F_{n-1}

Your task is to calculate the value of F_n for a given n.

Input

The only input line has an integer n.

Output

Print the value of F_n modulo 10^9+7.

Constraints

  • 0 \le n \le 10^{18}

Example

Input:

10

Output:

55