Description

定义\(F\)为斐波那契数列，被定义为：

\[F_0 = 0, F_1 = 1\]

\[F_n = F_{n-1}+F_{n-2}, n>1\]

而\(G\)为一个序列，定义为：

\[G_i = \sum_{a_1+a_2+...+a_m = i, a_k>0} \prod_{j\le m} {F_{a_j}}\]

对于给定的\(n\)，求\(G_n\mod 10^9+7\)。

Input

• 一个数n

Output

• 一个数\(G_n\mod 10^9+7\)。

Sample

Input

3

Output

5

Hint

\[3=1+1+1\ \ F_1\times F_1\times F_1 = 1\]

\[=2+1\ \ F_2\times F_1 = 1\]

\[=1+2\ \ F_1\times F_2 = 1\]

\[=3\ \ F_3 = 2\]

\[1+1+1+2 = 5\]

• 对于30%的数据，\(n\le 20\)
• 对于50%的数据，\(n\le 5000\)
• 对于70%的数据，\(n\le 10^7\)
• 对于100%的数据，\(n\le 10^{18}\)