== include(page="template/taskheader" task_id="superbec") ==

Poveste şi cerinţă...

Marcel are N becuri, numerotate de la 1 la N, care pot lumina puternic, pot lumina slab sau pot sa nu lumineze deloc. Pentru a schimba straile becurilor, el poate apasa de cate ori vrea pe oricare dintre urmatoarele butoane:
 
1. butonul A, care modifica starea tuturor becurilor.
2. butonul B, care modifica starea becurilor cu indice par.
3. butonul C, care modifica starea becurilor cu indice impar.
4. butonul D, care modifica starea becurilor cu indice de forma 3K+1, K numar natural
5. butonul E, care modifica starea becurilor cu indice de forma 3K+2, K numar natural
6. butonul F, care modifica starea becurilor cu indice de forma 5K, K numar natural
7. butonul G, care modifica starea becurilor cu indice de forma 5K+2, K numar natural
8. butonul H, care modifica starea becurilor cu indice de forma 5K+3, K numar natural
9. butonul I, care modifica starea becurilor cu indice de forma 5K+4, K numar natural
 
Modificarea starii unui buton se realizeaza in felul urmator: daca becul era stins, el urmeaza sa lumineze slab; daca lumina slab, urmeaza sa lumineze puternic; daca lumina puternic, urmeaza sa nu mai lumineze deloc.
 
Initial toate becurile sunt stinse. Marcel apasa de M ori butoane aleatoare, iar la final isi noteaza starea fiecarui bec. El se intreaba care este numarul de moduri de a obtine starea respectiva, tot din M mutari, considerand ca starea initiala este aceeasi (toate becurile sunt stinse). Ordinea apasarii butoanelor nu conteaza (ABA se considera aceeasi secventa de mutari cu AAB).

h2. Date de intrare

Fişierul de intrare $superbec.in$ ...

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), reprezentand starea finala a becurilor.

h2. Date de ieşire

În fişierul de ieşire $superbec.out$ ...

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

h2. Restricţii

h2. Restricţii si precizari

* $... ≤ ... ≤ ...$

* Un mod de a apasa de M ori butoanele se considera ca obtine sirul dat in input daca exista o modalitate de a asocia fiecarui caracter '?' din input unul dintre caracterele '0', '1' sau '2' astfel incat codificarea sirului de becuri din input sa fie identica cu codificarea sirului de becuri asa cum arata ele dupa cele M apasari de butoane
* M<=1.000.000.000
* N<=10.000
* T<=100
* pentru 75% din punctaj, N*T<=1.000

h2. Exemplu
table(example). |_. superbec.in |_. superbec.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|2
10 5
0120122101
7 3
?????0?
|

|
h3. Explicaţie