#描述#
一个有n+1个顶点{ 0, 1, ..., n } 和2n-1条边的图叫做“n-fan图”定义如下：
顶点0与其他n个顶点均用一条边相连，顶点k与顶点k+1用一边相连（1<=k<n）。举个例子，下面这个图就是4个顶点和5条边的“3-fan图”。
现在的问题就是：有多少生成树在这个“n-fan图”中？
生成树是包括所有顶点的子图，而且包括一些边使得子图是连通的，没有环。
下面就是3个顶点的“2-fan图”的所有生成树。

#格式#
##输入格式##
有多组数据，对于每组数据，有一个整数n(1&lt=n&lt=10000)，表示“n-fan图”的n，n=0表示输入结束。

##输出格式##
输出“n-fan图”中所有不同的生成树的数目，并把结果模10000。

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

1
2
3
0

##样例输出1##

1
3
8

#限制#
1000ms
32768KB

#提示#

#来源#
SCU Programming Contest 2006 Preliminary (modified by lily)