e-olymp
Competitions

ADA Classes - November 8

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
1
Output example #1
1
Input example #2
2
Output example #2
6