Background

Source: 2011 China CTT Problem Defense.

Problem 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