2181 - 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

Rezolvare

MOD = 1000003  

def calculate_inversion_sum(n):
    total_inversions = 0
    factorial = 1


    for i in range(1, n + 1):
        factorial *= i

        current_inversions = i * (n - i)

        total_inversions += current_inversions

        total_inversions %= MOD

    return total_inversions

def main():
    n = int(input())

    inversion_sum = calculate_inversion_sum(n)
    print(inversion_sum)

if __name__ == "__main__":
    main()