## 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