说明

时间限制：1 Sec 内存限制：256 MB 输入文件：ygraph.in 输出文件：ygraph.out

我们定义：一棵树，不存在度数大于等于 $4$ 的顶点，且恰好有 $1$ 个度数为 $3$ 的顶点，称它为 Y 字图。

给定顶点数 $N$，请求出顶点数为 $N$ 的 Y 字图的种类数，对 $10^9+7$ 取模。

同构的两棵树算作同一个种类。两棵树结构完全一样，只是节点编号不同，就称为树同构。可参考样例 2。

输入格式

第一行一个整数 $N$。

输出格式

输出顶点数为 $N$ 的 Y 字图的种类数模 $10^9+7$ 的结果。

样例

样例 1

4

1

样例说明：

顶点数为 $4$ 的Y字图只有下图所示的 $1$ 种。Y字图至少要有 $4$ 个顶点。

样例 2

7

3

样例说明：

顶点数为 $7$ 的Y字图有下图所示的 $3$ 种。

样例 3

100

817

样例 4

314159265358979323

92208567

样例说明：

$N$ 可能非常大。

数据范围

对于 100% 的数据，$4 \le N \le 10^{18}$。