inversum

Cerința

Fie o permutare $P$ a mulțimii ${1, 2, 3, … N}$. Se numește inversiune o pereche $(i, j), i < j$ pentru care $P_i > P_j$. Fie funcția $M(N)$ = suma numărului de inversiuni a fiecărei permutare a numerelor ${1, 2, 3, … N}$. Pentru $N$ dat, să se calculeze $M(N)$ modulo $1000003$.

Date de intrare

Programul citește de la tastatură numărul $N$.

Date de ieșire

Programul va afișa pe ecran numărul $S$, reprezentând valoarea $M(N)$ modulo $1000003$.

Restricții și precizări

• $1 ≤ N ≤ 1.000.000$

Exemplu:

Intrare

3

Ieșire

9