Integer lqp Partition Sum

Given a positive integer N, consider an ordered partition of N into positive integers: that is, a sequence a₁, a₂, …, a_m such that m > 0, each a_i > 0 and a₁ + a₂ + … + a_m = N.

Define the Fibonacci sequence as follows:

$$F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1}+F_{n-2}\quad (n>1). $$

For each partition, its weight is defined as:

$$\prod_{i=1}^{m}F_{a_i}.$$

Your task is to compute the sum of weights over all possible partitions of N, i.e., $$\sum_{m>0}\sum_{a_1+\cdots+a_m=N \atop a_i>0}\prod_{i=1}^{m}F_{a_i} \pmod{10^9+7}.$$

Note: The answer can be very large, so output it modulo 10^9+7.

## inputFormat

The input consists of a single line containing a positive integer N.

## outputFormat

Output a single integer, the sum of weights of all partitions of N modulo 10^9+7.

## sample

1

1

$$