== include(page="template/taskheader" task_id="mergesort") ==

Marele Intelept a venit sa va explice algoritmul MergeSort. Algoritmul MergeSort este folosit pentru a sorta siruri. Acesta functioneaza in felul urmator: Fie permutarea V si functia recursiva $MergeSort(left, right$ care sorteaza sirul $V$ pe intervalul $(i,j)$. La inceput se apeleaza functia $MergeSort(1,N)$ pentru a sorta tot vectorul. Functia $MergeSort(left, right)$ functioneaza in felul urmator: se determina mijlocul intervalulul $middle = (left + right) / 2$ si se apeleaza pe rand functiile $MergeSort(left, middle)$ si $MergeSort(middle + 1, right)$, dupa care cele $2$ siruri tocmai sortate se interclaseaza obtinandu-se sirul sortat intre pozitiile $left$ si $right$.

Marele Intelept a venit sa va explice algoritmul MergeSort. Algoritmul MergeSort este folosit pentru a sorta siruri. Acesta functioneaza in felul urmator: Fie permutarea V si functia recursiva $MergeSort(left, right)$ care sorteaza sirul $V$ pe intervalul $(left, right)$. La inceput se apeleaza functia $MergeSort(1, N)$ pentru a sorta tot vectorul. Functia $MergeSort(left, right)$ functioneaza in felul urmator: se determina mijlocul intervalulul $middle = (left + right) / 2$ si se apeleaza pe rand functiile $MergeSort(left, middle)$ si $MergeSort(middle + 1, right)$, dupa care cele $2$ siruri tocmai sortate se interclaseaza obtinandu-se sirul sortat intre pozitiile $left$ si $right$.

Programul ruleaza in felul urmator:
==code(cpp) |

int SOL = 0;

void mergesort(int left, int right) {

    ++SOL;
 
    bool sorted = true;
    for (int i = left + 1; i <= right; ++i)
        if (V[i - 1] > V[i]) {
            sorted = false;
            break;
        }
 

    if (left == right)
        return;

    int middle = (left + right) / 2;
    mergesort(left, middle);
    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(i,j)$, iar sirul de la $i$ la $j$ este deja sortat, atunci functia sa se opreasca. Mai exact daca se apeleaza functia $MergeSort(i,j)$, aceasta sa continuie doar daca sirul 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 % 666013$ 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 % 666013$.

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

h2. Restricţii