1423: #6185. 烷基计数

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例

样例输入

6

样例输出

17

数据范围与提示

1≤n≤400 1 \le n \le 400 1n400

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