faceid

Cerință

Andrei și Iustin se află într-o nesfârșită competiție pentru a obține postul de CEO la SloboziaSecurity, cea mai de succes companie de securitate cibernetică din întreaga Europă de Est.
Pentru a-i departaja, Marcel, robotul ce asigură interimatul companiei, le-a propus o problemă, iar primul care o va rezolva va fi cel ce va primi postul. Fiind prietenul lui Iustin și știind cât de mult înseamnă postul pentru el, te-ai hotărât să îl ajuți să rezolve problema în timp record.

Problema sună în felul următor: compania Pear, celebră pentru tehnologia ei FaceID, vrea ca această tehnologie să funcționeze în toate condițiile, chiar dacă anumite detalii din imaginea capturată de cameră lipsesc. Astfel, se consideră imaginea drept un tablou bidimensional $A$ de $n$ linii și $m$ coloane, fiecare element din tablou fiind un pixel din imagine, cu următoarea semnificație:

• dacă $A_{i j} = -1$, atunci informația din pixel lipsește;
• dacă $A_{i j} = 1$, atunci informația din pixel există, dar nu este relevantă;
• dacă $A_{i j} = 2$, atunci informația din pixel există și este relevantă.

Fie o secțiune a imaginii o mulțime conexă de pixeli cu informație relevantă și irelevantă, conexitatea acestora fiind dată de vecinătatea pe verticală sau orizontală. Rezolvarea problemei constă în a afla numărul de configurații posibile care respectă următoarele proprietăți:

• fiecare secțiune ocupă același loc în imagine;
• numărul de pixeli cu informație irelevantă și relevantă rămâne același pentru fiecare secțiune;
• fiecare secțiune are configurația diferită față de imaginea corectă.

Pentru că rezultatul poate fi foarte mare, se cere afișarea lui modulo $10^9+7$. Grăbește-te, Andrei deja se apropie de răspuns!

Date de intrare

Pe prima linie se găsesc numerele $n$ și $m$, reprezentând dimensiunile imaginii cu care veți lucra. Pe următoarele $n$ se află câte $m$ numere, al $j$-lea număr de pe linia $i + 1$ reprezentând valoarea pixelului $A_{i j}$ din imaginea corectă.

Date de ieșire

Pe ecran se va afișa un singur număr, reprezentând numărul de modalități dorit.

Restricții și precizări

• $1 \leq n \cdot m \leq 10^6$;
• $A_{i j} \in \{-1, 1, 2\}$;
• Se garantează că există cel puțin o secțiune.

Exemplul 1

stdin

3 4
1 2 -1 -1
2 1 -1 -1
-1 -1 1 2

stdout

5

Exemplul 2

stdin

7 5
1 2 -1 1 2
2 1 -1 2 1
-1 -1 -1 -1 -1
1 2 1 2 1
2 1 2 1 2
-1 -1 -1 -1 -1
1 2 -1 2 1

stdout

6275