@RabbitHu 2017-07-02T11:27:02.000000Z 字数 395 阅读 2123

烷基计数

题目

题目描述

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

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

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

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

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

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

现在已知碳原子个数 $n$ ，求对应的烷基有多少种同分异构体。由于答案可能很大，请对 $10^9+7$ 取模。

一行，一个整数 $n$ ，表示碳原子的个数。

一行，一个整数，表示 $n$ 个碳原子的烷基的同分异构体数目。
答案对 $10^9+7$ 取模。

991364623

$1 \le n \le 400$