mergesort(middle + 1, right);
    //interclaseaza cele 2 siruri de la left la middle, si de la middle + 1 la right

    .....
    .....

}
==

O calance a aprofundat acest algoritm si s-a decis sa faca urmatoarea optimizare: daca se apeleaza functia $MergeSort(left, right)$, iar sirul de la $left$ la $right$ este deja sortat, atunci functia sa se opreasca. Mai exact daca se apeleaza functia $MergeSort(left, right)$, aceasta sa continuie doar daca sirul intre $left$ si $right$ *NU* este sortat.

O calance a aprofundat acest algoritm si s-a decis sa faca urmatoarea optimizare: daca se apeleaza functia $MergeSort(left, right)$, iar sirul de la $left$ la $right$ este deja sortat, atunci functia sa se opreasca. Mai exact daca se apeleaza functia $MergeSort(left, right)$, aceasta sa continue doar daca sirul intre $left$ si $right$ *NU* este sortat.

Stiind ca la fiecare apelare a functiei $MergeSort$ aceasta incrementeaza cu $+1$ valoarea unui numar natural $SOL$ care initial este $0$, sa determine $SOL % 1000003$ dupa apelarea functiei $MergeSort(1, N)$ a tuturor permutarilor de ordin $N$.

Stiind ca la fiecare apelare a functiei $MergeSort$ aceasta incrementeaza cu $+1$ valoarea unui numar natural $SOL$ care initial este $0$, sa determine $SOL % 1.000.003$ dupa apelarea functiei $MergeSort(1, N)$ pe toate permutările de ordin $N$.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire $mergesort.out$ va contine pe prima linie un numar natural ce reprezinta $SOL % 1000003$.

Fişierul de ieşire $mergesort.out$ va contine pe prima linie un numar natural ce reprezinta $SOL % 1.000.003$.

h2. Restricţii