La prima oră de educaţie fizică cei N elevi, aliniaţi pe un singur rând, aşteaptă cu emoţie întâlnirea cu domnul profesor. Acesta apreciază efortul lor şi le propune ca la fiecare oră să-i găsească aliniaţi pe un rând, dar fiecare elev se poate muta cu cel mult un loc faţă de poziţia avută la prima oră.

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

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

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

Restricţii

• 0 < n < 300000

Exemple