Description

A fan of order n is a graph on the vertices { 0, 1, ..., n } with 2n-1 edges defined as follows:
Vertex 0 is connected by an edge to each of the other n vertices, and vertex k is connected by an edge to vertex k+1, for 1<=k<n. Here, for example, is the fan of order 3, which has four vertices and five edges.

The problem is: how many spanning trees are in such a graph?
A spanning tree is a subgraph containing all the vertices, and containing enough edges to make the subgraph connected yet not so many that it has a cycle.
The following shows all the spanning trees of fan of order 2.

Input

The input contains multiple test cases.
For each test case, there is one integer n (1<=n<=10000) in a line, indicate a fan of order n
A line with a single zero ends the input and should not be processed.

Output

The number of different spanning tree in the fan, moduled by 10000.

Sample Input

1
2
3
4
0

Sample Output

1
3
8
21

Source