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** (**1** ≤ **n** ≤ **50**).

#### Output

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

Input example #1

1

Output example #1

1

Input example #2

2

Output example #2

6