Problem Statement

We call a tree a "Y-shaped graph" if it has no vertices of degree $4$ or more and has exactly $1$ vertex of degree $3$.
Find the number of kinds of Y-shaped graphs with $N$ vertices, modulo $10^9+7$.

Input

$N$

The input satisfies the following constraints.

• $4 \le N \le 10^{18}$
• $N$ is an integer.

Output

Print the number of kinds of Y-shaped graphs with $N$ vertices, modulo $10^9+7$.

Sample

Sample 1

Input

4

Output

1

There is $1$ kind of Y-shaped graph with $4$ vertices, shown in the figure below. A Y-shaped graph has at least $4$ vertices.

Sample 2

Input

7

Output

3

There are $3$ kinds of Y-shaped graphs with $7$ vertices, shown in the figure below.

100

817

314159265358979323

92208567