E山坡

Description:

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

 

          *

   *   *  /\

*  /\  /\/  \

/\/  \/      \

 

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

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

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

Input:

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

Output:

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

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

Sample Input:

6

Sample Output:

4

Note:

 

本题由旧版NOJ导入，来源：NUAA_李元