== include(page="template/taskheader" task_id="mojosort") ==
Ameţit după petrecerea răufăcătorilor, Mojo Jojo s-a dus la Profi să îşi cumpere *N* banane numerotate cu indici distincţi de la *1* la *N* (acestea formează o permutare). Cu cât indicele unei banane este mai mare, cu atât banana este mai gustoasă. Ca orice altă maimuţă de speţă nobilă, Mojo Jojo preferă să păstreze ce e mai bun la sfârşit. Din acest motiv, acesta şi-ar dori să le mănânce în ordine de la banana cu indicele cel mai mic (banana cu indicele *1*), până la banana cu indicele *N*.
!{width: 300px; float: right; margin: 10px}problema/mojosort?mojojojo.png!
Ameţit după petrecerea răufăcătorilor, Mojo Jojo s-a dus la Profi să îşi cumpere $N$ banane numerotate cu indici distincţi de la $1$ la $N$ (acestea formează o permutare). Cu cât indicele unei banane este mai mare, cu atât banana este mai gustoasă. Ca orice altă maimuţă de speţă nobilă, Mojo Jojo preferă să păstreze ce e mai bun la sfârşit. Din acest motiv, acesta şi-ar dori să le mănânce în ordine de la banana cu indicele cel mai mic (banana cu indicele $1$), până la banana cu indicele $N$.
Din păcate, Mojo este mult prea ameţit ca să stea să sorteze banane după bunul plac, motiv pentru care le va mânca în ordinea în care le-a cumpărat. Fiind un geniu în bananologie, Mojo a definit costul unei astfel de permutări ca fiind numărul de inversiuni. Înainte de a se apuca de mâncat, Mojo s-a hotărât să minimizeze numărul de inversiuni ale permutării având la dispoziţie două tipuri de operaţii:
* __Monkey Shot__: Mojo alege două elemente consecutive din permutare şi le inversează
* __Monkey Punch__: Mojo dă cu pumnul în masă şi toate bananele se permută random cu probabilitate uniformă (se dă __random shuffle__ la permutare)
Deşi Mojo Jojo este un geniu în algoritmică şi programare competitivă, acesta nu se simte suficient de bine cât să deducă o strategie optimă de minimizare a numărului de inversiuni într-o permutare. Dându-se un număr natural *K*, Mojo Jojo poate să aplice maxim *K* operaţii descrise mai sus. Calculaţi __expected value__ ale numărului de inversiuni dacă Mojo ar aplica o strategie optimă.
Deşi Mojo Jojo este un geniu în algoritmică şi programare competitivă, acesta nu se simte suficient de bine cât să deducă o strategie optimă de minimizare a numărului de inversiuni într-o permutare. Dându-se un număr natural $K$, Mojo Jojo poate să aplice maxim $K$ operaţii descrise mai sus. Calculaţi __expected value__ ale numărului de inversiuni dacă Mojo ar aplica o strategie optimă.
h2. Date de intrare
Fişierul de intrare *$mojosort.in$* conţine pe prima linie *T*, reprezentând numărul de teste. Urmează apoi *T* perechi de linii: pe prima dintre acestea se citesc două numere întregi *N* şi *K*, cu semnificaţia din enunţ, iar pe cea de a doua linie se citesc *N* numere întregi distincte, despărţite prin câte un spaţiu, reprezentând indicii bananelor în ordinea în care le-a cumpărat Mojo Jojo.
Fişierul de intrare $$mojosort.in$$ conţine pe prima linie $T$, reprezentând numărul de teste. Urmează apoi $T$ perechi de linii: pe prima dintre acestea se citesc două numere întregi $N$ şi $K$, cu semnificaţia din enunţ, iar pe cea de a doua linie se citesc $N$ numere întregi distincte, despărţite prin câte un spaţiu, reprezentând indicii bananelor în ordinea în care le-a cumpărat Mojo Jojo.
h2. Date de ieşire
În fişierul de ieşire $mojosort.out$ va conţine răspunsul pentru fiecare din cele T
teste. Puteţi alege să afişaţi aceste numere în două moduri:
* __mojo-mode__: afişaţi un număr *R = P * Q^-1^ modulo 10^9^ + 7*, unde prin *X^-1^* s-a notat inversul modular al lui *X* faţă de *10^9^ + 7*, iar răspunsul este *P / Q*, cu *P* şi *Q* numere naturale, prime între ele
* __mojo-mode__: afişaţi un număr $R = P * Q^-1^ modulo 10^9^ + 7$, unde prin $X^-1^$ s-a notat inversul modular al lui $X$ faţă de $10^9^ + 7$, iar răspunsul este $P / Q$, cu $P$ şi $Q$ numere naturale, prime între ele
* __jojo-mode__: afişaţi un număr real reprezentând răspunsul exact cu o eroare de cel mult 10^-6^
Dacă alegeţi să afişaţi în mojo-mode vreun rezultat, afişaţi pe prima linie a fişierului mesajul “mojo”. Altfel, afişaţi mesajul “jojo”. Toate cele *T* rezultate trebuie afişate conform modelului selectat.
Dacă alegeţi să afişaţi în mojo-mode vreun rezultat, afişaţi pe prima linie a fişierului mesajul “mojo”. Altfel, afişaţi mesajul “jojo”. Toate cele $T$ rezultate trebuie afişate conform modelului selectat.
h2. Restricţii
● *1 ≤ N, T ≤ 300*
● *0 ≤ K ≤ 1 000 000 000*
● Dacă alegeţi __jojo-mode__ veţi obţine *60%* din punctajul testului respectiv.
● Pentru *40%* din teste avem *N ≤ 50* şi *T ≤ 50*
* $1 ≤ N, T ≤ 300$
* $0 ≤ K ≤ 1 000 000 000$
* Dacă alegeţi __jojo-mode__ veţi obţine $60%$ din punctajul testului respectiv.
* Pentru $40%$ din teste avem $N ≤ 50$ şi $T ≤ 50$
h2. Exemplu
| jojo
0.000000
1.500000
| În primul test, Mojo poate interschimba poziţiile (*1*,*2*) şi (*2*,*3*), obţinând permutarea *1*,*2*,*3*. Această permutare are *0* inversiuni.
În al doilea test, Mojo rearanjează aleatoriu permutarea, iar numărul mediu de inversiuni este *1.5*.
| În primul test, Mojo poate interschimba poziţiile (1,2) şi (2,3), obţinând permutarea 1,2,3. Această permutare are 0 inversiuni.
În al doilea test, Mojo rearanjează aleatoriu permutarea, iar numărul mediu de inversiuni este 1.5.
|
|2
3 2
