favorite We need a little bit of your help to keep things running, click on this banner to learn more

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).


One integer n (1n50).


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