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
```
