Enunț
În turnul arhivei funcționează o tiparniță care imprimă un număr x. Operatorul îi dă o listă de instrucțiuni. Unele instrucțiuni schimbă numărul, iar altele repetă un întreg bloc. Blocurile pot conține, la rândul lor, alte blocuri. Un program de câteva rânduri poate astfel descrie un număr uriaș de operații.
Cerință
Determină numărul imprimat după executarea fiecărui program. După fiecare adunare sau înmulțire se păstrează restul modulo 1 000 000 007. Instrucțiunea ADD a adună a la x. Instrucțiunea MUL a înmulțește x cu a. Perechea BEGIN k ... END execută instrucțiunile dintre cele două delimitatoare de exact k ori, în ordinea scrisă. END închide cel mai recent BEGIN încă neînchis. Un bloc cu k=0 nu modifică x. Un bloc poate fi gol.
Date de intrare
Prima linie conține T, numărul programelor independente. Pentru fiecare program se citesc n și valoarea inițială x, apoi exact n linii de instrucțiuni. Fiecare linie este ADD a, MUL a, BEGIN k sau END. Delimitatoarele BEGIN și END se numără în n. Numărul x se resetează pentru fiecare program.
Date de ieșire
Afișează pe câte o linie numărul final al fiecărui program, în intervalul [0,1 000 000 006].
Restricții
1 ≤ T ≤ 10; 1 ≤ n ≤ 1200; suma valorilor n dintr-un fișier este cel mult 1200. 0 ≤ x < 1 000 000 007; 0 ≤ a ≤ 10^9; 0 ≤ k ≤ 10^18. Programele sunt corect delimitate; adâncimea maximă este 500. Nu există alte instrucțiuni. Nu se cere afișarea pașilor intermediari. Pentru 20% din punctaj, nu există blocuri. Pentru alte 20%, există doar ADD, BEGIN și END. Pentru alte 20%, blocurile nu sunt imbricate. Ultimele 40% nu au restricții suplimentare.
Explicație
În primul program al exemplului 1, numărul pornește de la 1. La fiecare repetare se adună 2 și apoi se înmulțește cu 2: 1 → 6 → 16 → 36. Ordinea operațiilor contează. În al doilea program, blocul cu zero repetări este ignorat, iar instrucțiunea ADD 1 transformă 7 în 8.
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Întregul bloc se repetă de trei ori. Rezultatul unei repetări este intrarea următoarei.Mărește schema ↗Date de intrare
2
4 1
BEGIN 3
ADD 2
MUL 2
END
5 7
BEGIN 0
MUL 0
ADD 99
END
ADD 1
Date de ieșire
36
8
Exemplul 2
Date de intrare
2
2 2
MUL 3
ADD 1
2 2
ADD 1
MUL 3
Date de ieșire
7
9
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →