Xoca Nəsrəddin

Хoca Nəsrəddin $n\times n$ ölçülü cədvəlin sol yuxarı küncündədir, onun eşşəyi isə sağ aşağı küncdədir. Хoca yalnız sağa və ya aşağıya, eşşək isə yalnız sola və ya yuxarıya hərəkət edə bilər.

Onların eyni hüceyrədə görüşə biləcəyi neçə fərqli yol var? İki yol fərqli sayılır, əgər Хocanın və ya eşşəyin marşrutlarından ən azı biri digərlərindən fərqlidirsə.

Giriş verilənləri

Bir ədəd $n(1\le n\le 50)$.

Çıxış verilənləri

Bir ədəd çıxarın — Хoca və eşşəyin görüşə biləcəyi yolların sayı. Bu ədəd çox böyük ola biləcəyi üçün onu $9929$ modulu ilə çıxarın.

Nümunələr