logic

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 $2^{N-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 $2^N$ 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 $2^N$ 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 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 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 $2^{N-1}$ caractere din 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 $2^N$ 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 \leq N \leq 8$
• $1 \leq K \leq 10$
• Tabelele operațiilor logice sunt:
  
  

Exemplu 1

logic.in

1
2
&
&|
3
1101
0100
1000

logic.out

1
0
0

Explicație

$C = 1$, deci rezolvă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.

Exemplu 2

logic.in

2
2
&
&|
1

logic.out

3

Explicație

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