题目描述

小 F 有一根长度为 $n$ 的火柴，她想把这根火柴折成若干段，然后拼成若干个三角形（每一段都要用到不能浪费），然后将这些三角形按她喜欢的顺序排成一列。对三角形有以下的要求：

1. 不能退化（即任意两边之和严格大于第三边）
2. 三条边长均为正整数
3. 所有三角形两两相似

请统计有多少种可能的三角形序列。两个三角形序列 $A,B$ 不同当且仅当以下任一条件成立：：

1. 两个序列的三角形个数不同
2. 存在某个 $i$ 使得三角形 $A[i]$ 与三角形 $B[i]$ 不全等。

输入格式

一行一个整数 $n$ 。

输出格式

一行一个整数表示所求答案 $\bmod 10^9+7$ 的值。

样例

6

2

第一种： $(1,1,1),(1,1,1)$

第二种： $(2,2,2)$

每个三元组表示一个三角形的三条边长。

数据范围与约定

对于 $10\%$ 的数据， $n\leq 100$ 。

对于另外 $20\%$ 的数据， $n$ 是素数。

对于 $100\%$ 的数据， $n\leq 5\times 10^6$ 。