Competitions

# 1/8 ICPC Azerbaijan Qualification Preparation

# 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

3

Output example #1

30