== include(page="template/taskheader" task_id="minesweeper2") ==
Poveste şi cerinţă...
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$ ...
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
În fişierul de ieşire $minesweeper2.out$ ...
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3
1 -1 -1
|4
|
h3. Explicaţie
...
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") ==
