matcnt

Considerăm matricele pătratice cu $N$ linii şi $N$ coloane care memorează numai valori $0$ şi $1$ şi care îndeplinesc următoarele condiţii:

• au pe fiecare linie exact două valori egale cu $1$
• au pe fiecare coloană exact două valori egale cu $1$
• nu există în matrice patru valori de $1$ care să fie colţurile unei submatrice.

În exemplele de mai jos, prima matrice îndeplineşte cele trei condiţii, dar a doua matrice nu satisface condiţia a treia:

Cerință

Să se determine numărul acestor matrice. Pentru că acest număr poate fi foarte mare, se va afişa rezultatul modulo $200 \ 003$.

Date de intrare

Fişierul de intrare matcnt.in va conţine numărul natural $N$.

Date de ieșire

Fişierul de ieşire matcnt.out va conţine pe prima linie un număr natural reprezentând numărul matricelor, modulo $200 \ 003$.

Restricții și precizări

• $3 \leq N \leq 100 \ 000$
• Pentru $30\%$ din teste, $N \leq 50$
• Pentru alte $30\%$ din teste, $N \leq 1 \ 000$

Exemplul 1

matcnt.in

3

matcnt.out

6

Explicație

Cele $6$ matrice sunt:

011 011 101 101 110 110
101 110 011 110 011 101
110 101 110 011 101 011