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

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

Вхідні дані

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

Вихідні дані

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

Вхідні дані #1

3

Відповідь #1

30