Given the Fibonacci sequence $f_0 = x, f_1 = y$ and $f_i = f_{i-1} + f_{i-2}$ for $i > 1$ with $x, y$ are positive integers. Count the number of pairs $(x, y)$ such that the Fibonacci sequence initialized by these two numbers contains the number $k$. ($k$ cannot be $f_0$ or $f_1.$)

Input

• A single positive integer $k.$

Output

• Output the number of valid pairs modulo $10^9+7$.

Constraints

• $1 \le k \le 10^9.$

Example

Input

6

Output

7

Input

6969

Output

12361