#描述#
月光在研究n*m个方格中画回路时，首先需要了解他的算法会有多少种状态。月光将问题转化如下：一个只含左括号'('和右括号')'以及空格' '的字符序列，如果将其中的空格去除后是一个合法的括号匹配序列，则其是一种合法的状态。括号匹配序列的定义如下：空序列是一个括号匹配序列，如果S是括号匹配序列，那么(S)也是括号匹配序列，如果S，T都是括号匹配序列，那么ST也是括号匹配序列。比如 "()", "( )", " ( ()( ))" 都是合法的状态(引号是为了方便看清)。现在要求的是长度为n的合法状态有多少种状态，由于可能会有非常多的状态，而月光只想知道末4位数字。

#格式#
##输入格式##
每行一个正整数s(s&lt=1000)。

##输出格式##
对于每个s，输出合法状态的种数模10000。

#样例1#
##样例输入1##

1
2
3

##样例输出1##

1
2
4

#限制#
1000ms
32768KB

#提示#

#来源#
DK