Description

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

Input

每行一个正整数s(s<=1000)。

Output

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

Sample

Input

1
2
3

Output

1
2
4

Source: DK