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