调皮的数一

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

      数一很喜欢跑步~喜欢追逐风的脚步~

      但是数一永远改不了贪玩调皮的个性,他在跑步的时候经常跑到别的跑道上。假设数一在跑一条直线跑道,从左往右是1号跑道,2号跑道,3号跑道......如此类推,并且为了让数一同学更自由,总共有无限条跑道!数一需要跑n步才能到达终点,但是正如上面所说的,他每跑一步要么仍然在原跑道,要么蹿到相邻的跑道,当然数一是不会跑到1号跑道之外的,因为这是违背数一原则的!数一,顾名思义,肯定是从1号跑道开始跑步,同样的,最后必须回到1号跑道到达终点。那么请问数一有多少种方案来跑完这n步呢?(两种方案视为不同当且仅当两种方案的某一步所在的跑道不同)

Input

      多组数据,每组数据一个整数n(n≤1000)

Output

      对于每组数据,输出一个整数,表示满足题意的方案数。

Sample Input

2
3
5

Sample Output

2
4
21

Hint

n=2时,数一可以有1-2-1或者1-1-1两种方案

n=3时,数一可以有1-2-1-1或者1-1-2-1或者1-2-2-1或者1-1-1-1四种方案

Source

mathlover

Manager

Information
Solved Number51
Submit Number252
Problem Tags
math
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel