== include(page="template/taskheader" task_id="minesweeper2") ==
Akiyama a gasit un nou joc. Minesweeper pe o tabla de $2*N$(o tabla cu $2$ linii si $N$ coloane). Akiyama stie ca in Minesweeper casutele din matrice sunt de $2$ tipuri: cu bombe si fara. Cu toate acestea, acest joc este putin diferit: casutele de pe prima linie nu contin bombe (doar casutele de pe linia $2$ contin). Akiyama trebuie sa determine cate configuratii posibile sunt pentru cea dea doua linie, stiind pentru fiecare element de pe linia $1$ cu cate bombe se invecineaza.
Akiyama a gasit un nou joc. Minesweeper pe o tabla de $2*N$(o tabla cu $2$ linii si $N$ coloane). Akiyama stie ca in Minesweeper casutele din matrice sunt de $2$ tipuri: cu bombe si fara. Cu toate acestea, acest joc este putin diferit: casutele de pe prima linie nu contin bombe. Akiyama trebuie sa determine cate configuratii posibile sunt pentru cea de-a doua linie, stiind pentru anumite casute de pe linia $1$ cu cate bombe se invecineaza (pe verticala sau diagonala).
h2. Date de intrare
Fişierul de intrare $minesweeper2.in$ va contine pe prima linie un numar natural $N$. Pe urmatoarea linie vor fi $N$ numere naturale, elementul al $i$-lea reprezentand numarul de bombe cu care se invecineaza casuta de pe linia $1$, coloana $i$.
Fişierul de intrare $minesweeper2.in$ va contine pe prima linie un numar natural $N$. Pe urmatoarea linie vor fi $N$ numere naturale, elementul al $i$-lea reprezentand numarul de bombe cu care se invecineaza casuta de pe linia $1$, coloana $i$. Daca nu se cunoaste acest numar, pe pozitia respectiva se va afla valoarea -1.
h2. Date de ieşire
Fişierul de ieşire $minesweeper2.out$ va contine un singur numar natural reprezentand numarul configuratiilor posibile pentru linia $2$ a matricei, $modulo 666013$
Fişierul de ieşire $minesweeper2.out$ va contine un singur numar natural reprezentand numarul configuratiilor posibile pentru linia $2$ a matricei, $modulo 666013$.
h2. Restricţii
* $1 ≤ N ≤ 300.000$
* Pentru $20%$ din teste, $N ≤ 15$
* Pentru alte $30%$ se cunosc toate cele $N$ casute (nu o sa intalniti valoarea $-1$)
h2. Exemplu
table(example). |_. minesweeper2.in |_. minesweeper2.out |
|3
2 3 2
|1
1 -1 -1
|4
|
h3. Explicaţie
Exista o singura posibilitate: linia $2$ completata in intregime cu bombe.
Exista $4$ posibilitati: $011,010,101,100$ (unde cu $0$ am notat casuta libera si cu $1$ bomba)
== include(page="template/taskfooter" task_id="minesweeper2") ==
