题目描述

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

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

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

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

同理，其他常见烷基同分异构体数目如下表：

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

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

P.S. 2017.11.30 更新：化竞巨佬晴岚高二进国集保送北大了……

输入格式

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

输出格式

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

6

17

数据范围与提示

$1\le n\le 5000$