Delta Wave

A delta wave is a high amplitude brain wave in humans with a frequency of 1 - 4 hertz which can be recorded with an electroencephalogram (EEG) and is usually associated with slow-wave sleep (SWS).

-- from Wikipedia

Researchers have discovered a new kind of species called "otaku", whose brain waves are quite strange. The delta brain waves for the otaku can be approximated by a polygonal line in the 2D coordinate system. The line is a route from point (0, 0) to (N, 0), and it is moves only to the right (up, down or straight) at every step. It never dips below the x axis.

For example, here are all 9 kinds of delta waves for N = 4:

Given N, you are asked to find out how many kinds of different delta waves an otaku has.

Input

There will be no more than 20 test cases. There is only one line for each case, containing an integer N (2 < N ≤ 10000)

Output

Output one line for each test case. Because the answer may be quite large, you need only output the answer modula 10100.

Sample Input

3
4

Sample Output

4
9

Turning it in

The submit project tag for this assignment is wave. For your convenience, here is a submission form for this assignment.

submit server
File 1
Control code:
file 1=wave.hs
Course=fun
Project=wave