== 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:
# Butonul $A$, care modifica starea tuturor becurilor.
# Butonul $B$, care modifica starea becurilor cu indice par.
# Butonul $C$, care modifica starea becurilor cu indice impar.
# Butonul $D$, care modifica starea becurilor cu indice de forma <tex> 3 \cdot K + 1 </tex>, <tex> K </tex> numar natural
# Butonul $E$, care modifica starea becurilor cu indice de forma <tex> 3 \cdot K + 2 </tex>, <tex> K </tex> numar natural
# Butonul $F$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K </tex>, <tex> K </tex> numar natural
# Butonul $G$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K + 2 </tex>, <tex> K </tex> numar natural
# Butonul $H$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K + 3 </tex>, <tex> K </tex> numar natural
# Butonul $I$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K + 4 </tex>, <tex> K </tex> 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), 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$ ...
Î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
* 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$, fiecarui caracter $a$ $0$ sau $1$ si fiecarui caracter $b$ $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.
h2. Restricţii
* $1 ≤ M ≤ 1.000.000.000$
* $1 ≤ N ≤ 100.000$
* $1 ≤ T ≤ 100$
* $... ≤ ... ≤ ...$
* **Subtask 1 (20 puncte)**: $1 ≤ T, N, M ≤ 10$
* **Subtask 2 (30 puncte)**: suma celor $T$ numere $N$ nu va depasi $10.000$ si $1 ≤ M ≤ 200.000$
* **Subtask 3 (20 puncte)**: suma celor $T$ numere $N$ nu va depasi $10.000$
* **Subtask 4 (30 puncte)**: restrictiile initiale
h2. Exemplu
table(example). |_. superbec.in |_. superbec.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10
5 1
01010
6 3
0a1?0?
10 5
01?02b?10?
7 3
b?a??0?
15 20
?22??222?a?bb10
20 56
?a?02ab22?b2?a?1?a1?
27 21
0?20?02??2122a?21?0?a?a10??
27 16
0?1a?0a0?a1a1?a?12a?aa?a0?a
30 10
???????a???a?????b????1???b??1
40 100
2??2??1???1??1??0??2??b?b2?????1???2?0??
| 1
3
1
36
1287
0
0
0
1109
48903492
|
h3. Explicaţie
...
Primul test: singurul mod valid de a apasa butonul este: $B$
Al doilea test: cele $3$ moduri valide de a apasa butoanele sunt: $BHI$, $GHI$, $HII$
Al treilea test: singurul mod valid de a apasa butoanele este: $BCCDI$
Celelalte teste: Credeti comisia pe cuvant!
== include(page="template/taskfooter" task_id="superbec") ==
