提示: 欢迎访问OurACM平台。
Problem 2074 Number of methods

Accept: 106    Submit: 185
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

有n个石子连成一排,先要把这些石子拿光,刚开始可以任取一个,接下去只能取“有相邻的石子被取走”的石子,例如刚开始有5个石子,刚开始取走第3个,第二步只能取第2或第4个,以此类推。给出n,问将石子取光的方法有多少种。两种取法只要有某次取的石子不一样就视为不同。

Input

有多组测试数据,每组数据输入一个整数n(1<=n<=100)。

Output

每组数据输出一行,为将石子取光的方法数,结果模1000000007。

Sample Input

1 2

Sample Output

1 2

Source

FOJ有奖月赛-2012年3月

Submit  Back  Status  Discuss