#6185. 烷基计数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: RabbitHu

题目描述

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

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

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

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

chem.png

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

n 同分异构体数目
1 1
2 1
3 2
4 4
5 8
6 17

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

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

输入格式

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

输出格式

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

样例

样例输入

6

样例输出

17

数据范围与提示

1 \le n \le 400

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