Preparing NOJ

E山坡

1000ms 65536K

Description:

NUPT中有一座高山,这座山的山坡是由许多片段的45度斜坡构成,并且每一段斜坡不是上坡就是下坡。

 

          *

   *   *  /\

*  /\  /\/  \

/\/  \/      \

 

在我们眼前的所见的任何宽度为n个单位的山棱形状,可以轻松地观察到所有山顶的位置。(就是上图中*号标记的位置)

请问有多少种山棱线的形状,使得所有山顶的位置由左而右非递减呢?(也就是说山顶的高度从左至右非递减)

所有的山棱线都必须完整,也就是说左右两端都必须是高度为0的山脚,而且不能有任何山谷的位置隐没在地平线底下。


Input:

输入仅包含一个数字n,n一定会是偶数,因为会有相同片段数量的上坡以及下坡。n<=3000


Output:

请输出山顶位置由左而右非递减的山棱线形状总数。

由于答案可能很大,你只要输出以十进位表示时,它的最后9位数即可。


Sample Input:

6

Sample Output:

4

Note:

 

本题由旧版NOJ导入,来源:NUAA_李元

Info

NOJ

Provider NOJ

Code NOJ1172

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet