Given the Fibonacci sequence f0=x,f1=y and fi=fi−1+fi−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 f0 or f1.)
### Input
- A single positive integer k.
### Output
- Output the number of valid pairs modulo 109+7.
### Constraints
- 1≤k≤109.
### Example
Input
6
Output
7
Input
6969
Output
12361
