scaune

La un concurs de dans participa n perechi. Pentru fiecare pereche, baiatul si fata au pe spate scris acelasi numar natural din multimea {1, 2, …, 2n}.
Pot exista doua sau mai multe perechi care au pe spate acelasi numar.
Lânga un perete al salii de dans se afla un sir de scaune numerotate cu numerele 1, 2, 3, ..., 2n.
Dupa fiecare proba, perechile se aseaza astfel încât diferenta în valoare absoluta dintre numerele asociate scaunelor alese de baiatul si fata din pereche sa fie egala cu numarul scris pe spatele lor.

Cerinta
Sa se scrie un program care sa determine numarul de modalitati distincte de asezare a perechilor de dansatori care sa respecte regula din enunt.

Date de intrare
Fisierul de intrare scaune.in are pe prima linie numarul natural n.

Date de iesire
Fisierul de iesire scaune.out va contine pe prima linie numarul cerut modulo 30103 (restul împartirii numarului cerut la 30103).

Restrictii si precizari
0<n<1001
n împartit la 4 da restul 0 sau 1.
Pe un scaun se poate aseza o singura persoana.
Doua modalitati de asezare pe scaune sunt considerate distincte daca exista doua scaune pe aceeasi pozitie (unul în prima modalitate, celalalt în cea de-a doua) cu numere diferite.

Exemplu