Ходжа Насреддін

Ходжа Насреддін знаходиться в лівій верхній клітинці таблиці розміром $n\times n$, а його віслюк — у правій нижній. Ходжа може рухатися лише вправо або вниз, а віслюк — тільки вліво або вгору.

Скількома способами вони можуть зустрітися в одній клітинці? Два способи вважаються різними, якщо в них хоча б один із маршрутів Ходжі або віслюка відрізняється від іншого.

Вхідні дані

Одне число $n(1\le n\le 50)$.

Вихідні дані

Виведіть одне число — кількість способів, якими Ходжа і віслюк можуть зустрітися. Оскільки це число може бути дуже великим, виведіть його за модулем $9929$.

Приклади