Problem Description

Define a sequence:

$f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)$

where $a, b$ are positive integers, and $n \geq 2$.

The question is how many pairs $(a, b)$ exist such that $k$ appears in this sequence and is not one of the first two terms.

Since the answer may be very large, you only need to output the result modulo $10^9 + 7$.

Input Format

A single line containing an integer $k$.

Output Format

A single line containing a number, representing the result modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

19260817

Sample Output #1

34166325

Sample Input #2

1000000000

Sample Output #2

773877569

Notes

$1 \leq k \leq 10^9$

见题面 Input 部分

见题面 Output 部分