Se numeşte pătrat magic de ordin N o matrice cu 3 linii şi 3 coloane cu elemente întregi nenegative (mai mari sau egale cu 0) cu proprietatea că suma elementelor oricărei linii şi oricărei coloane este N.

Cerinţă

Scrieţi un program care să determine numărul pătratelor magice de ordin N modulo 30103.

Date de intrare

Fişierul de intrare patrat.in conţine pe prima linie numărul N.

Date de ieşire

Fişierul de ieşire patrat.out va conţine numărul pătratelor magice de ordin N modulo 30103.

Restricţii şi precizări

• 1 <= N <= 1 000 000

Exemple

patrat.in

2

patrat.out

21

patrat.in

5

patrat.out

231