Fişierul intrare/ieşire:superbec.in, superbec.outSursăJunior Challenge 2016
AutorAlexandru PetrescuAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test0.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Superbec

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  3 \cdot K + 1 ,  K numar natural
  5. Butonul E, care modifica starea becurilor cu indice de forma  3 \cdot K + 2 ,  K numar natural
  6. Butonul F, care modifica starea becurilor cu indice de forma  5 \cdot K ,  K numar natural
  7. Butonul G, care modifica starea becurilor cu indice de forma  5 \cdot K + 2 ,  K numar natural
  8. Butonul H, care modifica starea becurilor cu indice de forma  5 \cdot K + 3 ,  K numar natural
  9. Butonul I, care modifica starea becurilor cu indice de forma  5 \cdot K + 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).

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.

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  10^9 + 7 a numarului de moduri de a apasa de M ori butoanele si de a obtine sirul dat in input, la testul respectiv.

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

Exemplu

superbec.insuperbec.out
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

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!

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?