Hodja Nasreddin

Hodja Nasreddin is located in the top-left cell of an $n\times n$ grid, while his donkey is in the bottom-right cell. Hodja can only move right or down, and the donkey can only move left or up.

How many ways can they meet in the same cell? Two ways are considered different if at least one of the routes of Hodja or the donkey is different from the other.

Input

A single integer $n(1\le n\le 50)$.

Output

Print a single number — the number of ways in which Hodja and the donkey can meet. Since this number may be very large, print it modulo $9929$.

Examples