#812. #6185. 烷基计数

#6185. 烷基计数

题目描述

众所周知,大连 24 中是一所神奇的学校,在那里,化竞的同学很多都擅长写代码。 有一天,化学不及格的胡小兔向化竞巨佬晴岚请教化学题: “nn 个碳原子的烷基共有多少种同分异构体?” 刚刚得了化竞全市第一的晴岚听了,认为这道题十分简单,建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道,于是晴岚给胡小兔画了个图——例如 n=4n = 4 时(即丁基),有 44 种同分异构体: 同理,其他常见烷基同分异构体数目如下表:

nn 11 22 33 44 55 66
同分异构体数目 11 22 44 88 1717

现在已知碳原子个数 nn,求对应的烷基有多少种同分异构体。 P.S. 2017.11.30更新:化竞巨佬晴岚高二进国集保送北大了……

输入格式

输入一行,一个整数 nn,表示烷基中碳原子的数目。

输出格式

输出该烷基同分异构体的数目,对 109+710^9 + 7 取模。

6
17

数据范围与提示

1≤n≤4001 \le n \le 400 注意:这里的烷基计数不用考虑空间异构,能否稳定存在等各种特殊情况。也就是说,你要求的是 nn 个点的每个点度数不超过 44 且根的度数不超过 33 的有根树的数目。