În jurul mesei rotunde se află N cavaleri. Aceştia iau în unanimitate decizia ca la următoarele întâlniri fiecare cavaler să se poată muta cu cel mult un loc faţă de locul iniţial.

Cerinţă
Aflaţi numărul de moduri în care se pot aranja cei N cavaleri (modulo 9973)

Date de intrare
Fişierul de intrare cavaleri.in conţine pe prima linie numărul de cavaleri n.

Date de ieşire
Fişierul de ieşire cavaleri.out va conţine o singură linie pe care va fi afişat numărul de  moduri în care se pot aranja cei N cavaleri (modulo 9973).

Restricţii

• 3 < n < 100000

Exemple