Costel este pasionat de circuitele logice. El are la dispoziție două tipuri de circuite logice simple: circuit ȘI, respectiv circuit SAU. Circuitele logice simple au două intrări și o ieșire.

La fiecare intrare în circuit se poate introduce un bit 0 sau un bit 1, iar circuitul este capabil să calculeze operația logică respectivă (ȘI ori SAU) și să trimită rezultatul obținut la ieșire. Costel a învățat că poate combina mai multe circuite simple pentru a obține circuite complexe astfel: leagă ieșirea unui circuit de orice tip la una din intrările altui circuit, deci rezultatul obținut la ieșirea dintr-un circuit se transmite la intrarea celuilalt. În acest fel se pot construi circuite complexe, care au mai multe intrări și o singură ieșire.

Ultima descoperire a lui Costel este circuitul logic piramidal (prescurtat CLP), care are structura următoare:

• Circuitul cu un singur nivel este cel mai simplu tip de circuit și este compus dintr-un circuit ȘI ori dintr-un circuit SAU;
• Pentru un circuit cu mai multe nivele avem:

- pe nivelul 1 se găsește un singur circuit (ȘI ori SAU);

– pe nivelul 2 se găsesc două circuite simple de oricare tip; ieșirea primului circuit este conectată la intrarea 1 a circuitului de pe nivelul 1, iar ieșirea celui de-al doilea circuit este conectată la intrarea 2 a circuitului de pe nivelul 1;

– pe nivelul N sunt 2N-1 circuite simple; ieșirile primelor două circuite de pe linia N sunt conectate la intrările primului circuit de pe nivelul N - 1, ieșirile următoarelor două sunt conectate la intrările celui de-al doilea circuit de pe linia N - 1 etc;

Exemplu de CLP cu 2 nivele:

Într-un CLP cu N nivele avem 2N intrări, corespunzătoare circuitelor de pe nivelul N. La fiecare intrare se poate introduce un bit 0 sau un bit 1, deci un șir de 2N biți.

Pentru circuitul din figura de mai sus presupunem că la cele patru intrări ale circuitelor de pe nivelul 2 avem, în ordine, biții 0111. La ieșirea din circuit (ieșirea circuitului simplu de pe primul nivel) se obține valoarea 0, deoarece acest circuit este echivalent cu expresia logică ((0 și 1) și (1 sau 1)).

Cerința 1 (30 de puncte)

Pentru un CLP dat, cu N nivele și pentru K șiruri de biți date la intrarea circuitului, să se determine, pentru fiecare șir, valoarea calculată la ieșirea din circuit.

Cerința 2 (70 de puncte)

Pentru un CLP dat, cu N nivele și cunoscând valoarea obținută la ieșire (0 sau 1), să se determine numărul șirurilor de biți distincte ce pot fi date la intrare pentru a se obține valoarea specificată la ieșire. Rezultatul poate fi un număr foarte mare, de aceea el se va afișa modulo 666013.

Date de intrare

Pe prima linie a fișierului logic.in se găsește un număr natural C (C = 1 pentru cerința 1, respectiv C = 2 pentru cerința 2). Pe a doua linie se găsește numărul natural N, reprezentând numărul de nivele ale circuitului; Pe următoarele N linii (linii de la 3 la N + 2) se găsește descrierea circuitului, fără spații între caractere, astfel:

• pe linia 3 un caracter & sau |, unde prin caracterul ‘&’ se codifică un circuit ȘI, iar prin caracterul | se codifică un circuit SAU;
• pe linia 4 două caractere din mulțimea {&, |};
• pe linia 5 patru caractere din mulțimea {&, |};
• …
• pe linia N + 2 avem 2N-1 caractere mulțimea {&, |};

Pentru cerința 1:

• Pe linia N + 3 avem un număr natural K, reprezentând numărul șirurilor de biți date la intrarea în circuit;
• Pe fiecare dintre următoarele K linii avem câte un șir compus din 2N biți (caractere 0 sau 1), reprezentând șirul de biți dat la intrare;

Pentru cerința 2:

• Pe linia N + 3 avem un număr natural din mulțimea {0, 1}, reprezentând valoarea pe care circuitul trebuie să o scoată la ieșire.

Date de ieșire

Pentru cerința 1 se vor afișa în fișierul logic.out, pe linii separate, K numere naturale din mulțimea {0, 1}, cu semnificația din enunț. Pentru cerința 2 se va afișa în fișierul logic.out un număr natural cu semnificația din enunț.

Restricții și precizări

• 1 ≤ N ≤ 8
• 1 ≤ K ≤ 10
• Tabelele operațiilor logice sunt:

Exemplul 1:

logic.in

1
2
&
&|
3
1101
0100
1000

logic.out

1
0
0

Explicație

C = 1, deci rezovăm cerința 1. Pentru șirul de biți 1101 valoarea obținută la ieșirea din circuit este rezultatul evaluării expresiei: ((1 și 1) și (1 sau 0)) = (1 și 1) = 1.

Pentru șirul de biți 0100 valoarea obținută la ieșirea din circuit este rezultatul evaluării expresiei:
((0 și 1) și (0 sau 0)) = (0 și 0) = 0

Pentru șirul de biți 1000 valoarea obținută la ieșirea din circuit este rezultatul evaluării expresiei:
((1 și 0) și (0 sau 0) = (0 și 0) = 0

Exemplul 2:

logic.in

2
2
&
&|
1

logic.out

3

Explicație

C = 2, deci rezovăm cerința 1. Sunt 3 șiruri de 4 biți pentru care se obține valoarea 1 la ieșirea din
circuit: 1101, 1110, 1111.