3903布阵

3903   布阵

题目描述

黑暗军团在城外的草地上布阵，如果把草地划分成很多大小一样的方格，看成无限大的棋盘，军团从中心点出发，每次只能向上或向左或向右移动一步（移动的过程中，走过的格子不能再次进入）。就能到达相邻的一个格子里，如果一共移动了N步，总共有多少种走法呢？

输入格式:

一个整数即Ｎ，N≤30。

输出格式:

输出步数。
输入样例 复制 
2
输出样例 复制 
7

说明

15
34
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型递推
难        度