Description

lqp is struggling to write problems and has no clue, which is frustrating.

He first thought of integer decompositions. Integer decomposition is an interesting problem. Given a positive integer $n$, an integer decomposition of $n$ is an ordered sequence such that for any $m>0$, $a_1,a_2,a_3,\cdots,a_m>0$, and $a_1+a_2+a_3+\cdots+a_m=n$. After long study, we found a very simple recurrence to count the total number of integer decompositions of $n$, but because that recurrence is too simple, if he gave such a problem, nobody would be interested.

Then lqp thought of Fibonacci numbers. Define $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n>1)$; $F_n$ is the $n$-th Fibonacci number. But computing the $n$-th Fibonacci number does not seem very hard either.

To make the contest more appealing, lqp racked his brain and came up with an interesting integer decomposition; let us call it: the lqp decomposition of an integer.

Like ordinary integer decompositions, an lqp decomposition of an integer is an ordered sequence with $m>0$, $a_1,a_2,a_3,\cdots,a_m>0$, and $a_1+a_2+a_3+\cdots+a_m=n$. However, instead of asking for the total number of decompositions, the lqp decomposition asks for something a bit harder.

For each decomposition, lqp defines its weight as $F_{a_1}F_{a_2}\cdots F_{a_m}$. He wants to know the sum of the weights over all decompositions.

In short, compute

$$\sum_{\substack{m>0\\a_1,\cdots,a_m>0\\a_1+\cdots+a_m=n}}\prod_{i=1}^mF_{a_i}$$

Since the answer can be very large, output it modulo $10^9 + 7$.

Input Format

The first line of input contains an integer $n$.

Output Format

Output one line with a single integer representing the answer.

3

5

Hint

Constraints:
For $60\%$ of the testdata, $1 \le n \le 10^9$.
For $100\%$ of the testdata, $1 \le n \le 10^{10000}$.

Sample explanation:
$F_0=0,F_1=1,F_2=1,F_3=2$.

For $n=3$, there are the following lqp decompositions:

$3=1+1+1$, the weight is $F_1\times F_1\times F_1=1\times1\times1=1$.

$3=1+2$, the weight is $F_1\times F_2=1\times1=1$.

$3=2+1$, the weight is $F_2\times F_1=1\times1=1$.

$3=3$, the weight is $F_3=2$.

Therefore, the answer is $1+1+1+2=5$.

Translated by ChatGPT 5