Description

一个有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图”的所有生成树。

Input

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

Output

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

Sample

Input

1
2
3
0

Output

1
3
8

Source: SCU Programming Contest 2006 Preliminary (modified by lily)