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$.

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ă.

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.

Date de ieșire

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 \times Q^{-1}\text{ 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.

Restricții și precizări

• $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$.

Exemplu

mojosort.in

2
3 2
3 1 2
3 1
3 2 1

mojosort.out

jojo
0.000000
1.500000

mojosort.in

2
3 2
3 1 2
3 1
3 2 1

mojosort.out

mojo
0
500000005

Explicaţie

Î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$.
$1.5 = 3/2 = 3\times2^{-1} = 500\ 000\ 005$ modulo $10^9+7$