Minesweeper 2

Minesweeper2

== 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. 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).

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 dea doua linie, stiind pentru anumite casute de pe linia $1$ cu cate bombe se invecineaza.

h2. Date de intrare

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