Se dau două numere N și M urmate de un șir de numere întregi nenule S de lungime impară N indexat de la 0. Asupra acestuia se vor efectua fix M operații de swap. O operatie reprezintă selectarea la întâmplare a doi indici (nu neapărat distincți) din intervalul [0, N – 1] și interschimbarea elementelor de pe pozițiile respective.
Se consideră că șirul este alternant dacă nu există elemente alăturate având același semn.
Cerinţă
Determinați probabilitatea ca la finalul celei de-a M-a operații, șirul să fie alternant. (Se garantează că există cel puțin o aranjare a șirului astfel încât acesta să fie alternant).
Se poate demonstra că probabilitatea cerută se poate reprezenta sub forma P / Q unde P si Q sunt prime între ele.
Date de intrare
Pe prima linie din fișierul alternant.in se află două numere naturale N și M.
Pe a doua linie din fișierul de intrare se află șirul S
Date de ieșire
Fişierul de ieşire alternant.out va conţine probabilitatea ca la finalul celei de-a M-a operații șirul să fie alternant, reprezentată sub forma , P și Q fiind definite mai sus.
Restricții și precizări
1 ≤ N ≤ 100Neste impar1 ≤ M ≤ 1 000 000 000- Pentru
75%din teste se garantează căN * M ≤ 1 000 000
Exemplu
alternant.in
3 2
1 2 -3
alternant.out
370370374
Explicatie
Fractia corespunzatoare exemplului este 24/81. Simplificata, fractia devine 8/27.