Description

In the Fibonacci integer sequence,$F_0$ = 0,$F_1$ = 1, and $F_n$ = $F_n$ − 1 + $F_n$ − 2 for $n ≥ 2$.

Format

Input

a single line containing $n$ (where $0 ≤ n ≤ 100,000,000,000$)

Output

print $F_n$ $mod$ $1000000007$ in a single line.

Samples

99999999999

669753982

Hints

An alternative formula for the Fibonacci sequence is

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix: