== 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: Se apeleaza o functie MergeSort(i,j) care sorteaza sirul intre pozi

Marele Intelept a venit sa va explice algoritmul MergeSort. Algoritmul MergeSort este folosit pentru a sorta siruri. Acesta functioneaza in felul urmator: Fie functia recursiva $MergeSort(i,j)$ care sorteaza sirul pe intervalul $(i,j)$. La inceput se apeleaza functia $MergeSort(1,n)$ pentru a sorta tot vectorul. Functia $MergeSort(i,j)$ functioneaza in felul urmator: se determina mijlocul intervalulul $mij = (i + j) / 2$ si se apeleaza pe rand functiile $MergeSort(i,mij)$ si $MergeSort(mij + 1, j)$, dupa care cele $2$ siruri tocmai sortate se interclaseaza obtinandu-se sirul nostru sortat.
 
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.
 
Stiind ca la fiecare apelare a functiei $MergeSort(i,j)$ 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$.

h2. Date de intrare