h2. Date de intrare

Fişierul de intrare $superbec.in$ va contine pe prima linie numarul T de teste. Structura fiecarui test este descrisa mai jos:
Pe prima linie se vor afla numerele N si M, iar pe urmatoarea linie, N caractere egale fie cu '0' (bec stins), fie cu '1' (bec care lumineaza slab), fie cu '2' (bec care lumineaza puternic), fie cu caracterul '?' (bec a carui stare ii este necunoscuta pana si lui Marcel), fie 'a' (din amintirile lui Marcel, bec a carui stare poate fi '0' sau '1'), fie 'b' (bec a carui stare poate fi '1' sau '2'), reprezentand starea finala a becurilor.

Fişierul de intrare $superbec.in$ va contine pe prima linie numarul $T$ de teste. Structura fiecarui test este descrisa mai jos:
Pe prima linie se vor afla numerele $N$ si $M$, iar pe urmatoarea linie, $N$ caractere egale fie cu $0$ (bec stins), fie cu $1$ (bec care lumineaza slab), fie cu $2$ (bec care lumineaza puternic), fie cu caracterul $?$ (bec a carui stare ii este necunoscuta pana si lui Marcel), fie $a$ (din amintirile lui Marcel - bec a carui stare poate fi $0$ sau $1$), fie $b$ (bec a carui stare poate fi $1$ sau $2$), reprezentand starea finala a becurilor.

h2. Date de ieşire

În fişierul de ieşire $superbec.out$ se vor gasi T linii, fiecare dand raspunsul la cate un test, raspunsul fiind un singur numar, reprezentand restul la impartirea cu 1.000.000.007 a numarului de moduri de a apasa de M ori butoanele si de a obtine sirul dat in input, la testul respectiv.

În fişierul de ieşire $superbec.out$ se vor gasi $T$ linii, fiecare dand raspunsul la cate un test, raspunsul fiind un singur numar, reprezentand restul la impartirea cu <tex> 10^9 + 7 </tex> a numarului de moduri de a apasa de $M$ ori butoanele si de a obtine sirul dat in input, la testul respectiv.

h2. Restricţii si precizari