Aqua er rökþrautaleikur sem spilaður er á rétthyrndu borði sem skipt er í $r$ raðir og $c$ dálka. Raðirnar eru númeraðar frá $1$ til $r$ neðan frá og upp, og dálkarnir eru númeraðir frá $1$ til $c$ frá vinstri til hægri. Reiturinn í $i$-tu röð og $j$-ta dálki er táknaður með $(i,j)$.

Borðinu er skipt í nokkur hornrétt samanhangandi svæði (búr) með lóðréttum og láréttum mörkum. Nákvæmar tiltekið er hvert búr ótómt hlutmengi af reitum borðsins. Hver reitur á borðinu tilheyrir nákvæmlega einu búri. Mengi reita í búri myndar samanhangandi þátt: Ef tveir reitir tilheyra sama búri er alltaf hægt að ferðast úr öðrum reitnum í hinn með því að fara eingöngu um reiti þess búrs, þannig að hvert skref sé færsla milli tveggja reita sem deila hlið.

Mynd A.1: Borð með 6 röðum, 7 dálkum og 8 búrum.

Í hverju búri hellir þrautahöfundurinn vatni frá efri brúnum búrsins. Vegna þyngdaraflsins rennur vatnið niður í reiti sem liggja lægra. Hann hellir vatni þannig að öll skilyrðin hér að neðan séu uppfyllt:

• Hver reitur er annaðhvort alveg fullur af vatni eða alveg tómur.

• Búr getur verið fullt af vatni, alveg tómt eða fyllt að hluta.

• Í hverju búri er til ákveðin vatnshæð $\ell$ þannig að allir reitir búrsins fyrir neðan þessa hæð eru fullir og allir reitir búrsins fyrir ofan þessa hæð eru tómir. Með öðrum orðum, látum $(r_1,c_1)$ og $(r_2,c_2)$ vera tvo reiti í sama búri þannig að $r_1 \le r_2$; ef reiturinn $(r_2,c_2)$ er fullur, þá verður reiturinn $(r_1,c_1)$ einnig að vera fullur.

• Búrin eru meðhöndluð óháð og aðskilið hvert frá öðru. Því gildir reglan hér að ofan ekki um reiti sem tilheyra ólíkum búrum.

Hér að neðan er dæmi um gilt borð:

Mynd A.2: Gilt borð.

Hér að neðan eru nokkur dæmi um ógild borð:

Mynd A.3: Ógilt borð — reitirnir $(5,5)$ og $(5,7)$ ættu annaðhvort báðir að vera fullir eða báðir tómir, þar sem þeir eru í sama búri og í sömu röð.

Mynd A.4: Ógilt borð — reitirnir $(4,2)$, $(4,3)$ og $(4,4)$ eru tómir, en þeir eru í sama búri og reiturinn $(5,2)$, sem er fullur af vatni.

Mynd A.5: Ógilt borð — reitir geta ekki verið aðeins fylltir að hluta.

Þrautahöfundurinn fylgir ekki aðeins reglunum hér að ofan, heldurætir hann einnig að fjölda fullra reita í hverri röð. Í sumum röðum vill hann að fjöldi fullra reita sé jafn ákveðnum föstum gildum, en setur engar skorður á aðrar raðir.

Verkefni þitt er að telja fjölda leiða til að hella vatni í búrin þannig að öllum reglum og kröfum hér að ofan sé fullnægt. Tvær leiðir teljast ólíkar ef og aðeins ef til er reitur sem er fullur í annarri leiðinni en tómur í hinni.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $r,c$ ($1 \le r,c \le 20$). Næstu $r+1$ línur lýsa borðinu samkvæmt eftirfarandi reglum:

• Hver lína inniheldur nákvæmlega $2\cdot c+1$ stafi, þar sem hver stafur er eitt af eftirfarandi: bil, undirstrik (_) eða lóðrétt strik (|).

• Allir stafir í sléttum sætisnúmerum í fyrstu og síðustu línunni eru undirstrik, sem sýna efri og neðri mörk borðsins.

• Hvert undirstrik í inntakinu, fyrir utan þau sem nefnd eru hér að ofan, táknar lárétt búrmörk milli tveggja samliggjandi reita í sama dálki.

• Fyrsti og síðasti stafurinn í öllum línum (nema þeirri fyrstu) eru lóðrétt strik, sem sýna vinstri og hægri mörk borðsins.

• Hvert lóðrétt strik í inntakinu, fyrir utan þau sem nefnd eru hér að ofan, táknar lóðrétt búrmörk milli tveggja samliggjandi reita í sömu röð.

Sjá sýnidæmin til glöggvunar.

Samkvæmt skilgreiningu:

• Ef engin lárétt búrmörk eru milli tveggja samliggjandi reita í dálki, þá tilheyra þessir tveir reitir sama búri.

• Ef engin lóðrétt búrmörk eru milli tveggja samliggjandi reita í röð, þá tilheyra þessir tveir reitir sama búri.

Síðasta línan inniheldur $r$ heiltölur $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) sem lýsa kröfum um fjölda fullra reita í hverri röð. Ef $x_i=-1$, þá getur ($r-i+1$)-ta röðin haft hvaða fjölda sem er af reitum með vatni. Annars verður fjöldi fullra reita í þessari röð að vera nákvæmlega $x_i$.

Tryggt er að borðið hefur í mesta lagi 20 búr.

Úttak

Úttakið inniheldur nákvæmlega eina heiltölu — fjölda gildra borða sem uppfylla gefin skilyrði, modulo $10^9+7$.

Sýnidæmi

Inntak 1

6 7
 _ _ _ _ _ _ _ 
| |  _ _|  _  |
| | |_ _| |_| |
| |_ _ _|  _ _|
| |  _ _| |   |
| | |_ _| |   |
|_|_ _ _|_|_ _|
6 3 7 2 2 2

Úttak 1

1

Skýring

Fyrsta sýnidæmið samsvarar mynd A.2 hér að ofan.

Inntak 2

2 3
 _ _ _ 
|     |
|_ _ _|
-1 -1

Úttak 2

3

Inntak 3

3 3
 _ _ _ 
|  _  |
| | | |
|_|_|_|
-1 1 1

Úttak 3

1