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$.

How many pairs $(a, b)$ are there such that $k$ appears in this sequence and is not one of the first two terms?

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

Input Format

One line containing an integer $k$.

Output Format

One line containing an integer, which is the answer modulo $10^9 + 7$.

19260817

34166325

1000000000

773877569

Hint

$1 \leq k \leq 10^9$.

Translated by ChatGPT 5