暂无测试数据。

Description

众所周知，大连 24 中是一所神奇的学校，在那里，化竞的同学很多都擅长写代码。

有一天，化学不及格的胡小兔向化竞巨佬晴岚请教化学题：

「\(n\) 个碳原子的烷基共有多少种同分异构体？」

刚刚得了化竞全市第一的晴岚听了，认为这道题十分简单，建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道，于是晴岚给胡小兔画了个图——例如 \(n=4\) 时（即丁基），有 \(4\) 种同分异构体：

现在已知碳原子个数 \(n\)，求对应的烷基有多少种同分异构体。

注意：这里的烷基计数不用考虑空间异构，能否稳定存在等各种特殊情况。也就是说，你要求的是 \(n\) 个点的每个点度数不超过 \(4\) 且根的度数不超过 \(3\) 的有根树的数目。

Format

Input

输入一行，一个整数 \(n\)，表示烷基中碳原子的数目。

Output

输出该烷基同分异构体的数目，对 \(10^9+7\) 取模。

Sample 1

Input

6

Output

17

Limitation

Data

\(1 \le n \le 5000\)

Time and Space

1s, 125MB.

Source

loj #6269

update by Shuchong