Competitions

# Hodja Nasreddin

Hodja Nasreddin is located in the upper left corner of the table of the size n × n, and his donkey is located in the lower right corner. Hodge goes only to the right or down, a donkey goes only to the left or up.

In how many ways they can meet in one cell? (Two ways are considered different if Hodja or donkey has different routes).

#### Input

One integer n (1n50).

#### Output

Print one number - the number of ways Hodja and donkey can meet. This number can be big, so print its value modulo 9929.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
Output example #1
30