Fibonacci Numbers

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