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