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 operație 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ța

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 * Q−1 (modulo 1.000.000.009), P și Q fiind definite mai sus.

Restricții și precizări

• 1 ≤ N ≤ 100
• N este impar
• 1 ≤ 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

Explicație

Fractia corespunzatoare exemplului este 24 / 81. Simplificată, fracția devine 8 / 27.