Occurrence of k in a Modified Fibonacci Sequence

We define a sequence as follows:

\(f(0)=a, \quad f(1)=b, \quad f(n)=f(n-1)+f(n-2)\) for \(n\ge2\),

where \(a\) and \(b\) are positive integers. For a given positive integer \(k\), count the number of pairs \((a,b)\) such that \(k\) appears in the sequence as a term other than the first two (i.e. \(k\neq a\) and \(k\neq b\)). Since the answer may be very large, output it modulo \(10^9+7\).

Note: A pair \((a,b)\) is counted if there exists an index \(n\ge2\) with \(f(n)=k\). It can be shown that for each fixed index \(n\ge2\) the equation \[ F(n-1)\,a+F(n)\,b=k \] (where \(F(\cdot)\) denotes the Fibonacci numbers with \(F(0)=0,\;F(1)=1\)) has solutions that form an arithmetic progression. The overall answer is the sum (over all valid \(n\)) of the number of positive solutions \((a,b)\) of the above linear Diophantine equation. Moreover, note that if \(F(n-1)+F(n)>k\) then no valid positive integer solution exists for that \(n\).

inputFormat

The input consists of a single line containing a positive integer \(k\).

\(1 \le k \le 10^{12}\) (for example).

outputFormat

Output a single integer: the number of pairs \((a,b)\) for which \(k\) appears as one of the terms \(f(n)\) with \(n\ge2\) (and thus \(k\neq a, k\neq b\)), modulo \(10^9+7\).

sample

3

3