Aqua on looginen pulmapeli, jota pelataan suorakulmaisella laudalla, joka on jaettu $r$ riviin ja $c$ sarakkeeseen. Rivit on numeroitu $1$:stä $r$:ään alhaalta ylös, ja sarakkeet on numeroitu $1$:stä $c$:hen vasemmalta oikealle. Rivillä $i$ ja sarakkeessa $j$ sijaitsevaa ruutua merkitään $(i,j)$.

Lauta on jaettu pysty- ja vaakasuorilla rajoilla useisiin ortogonaalisesti yhtenäisiin alueisiin (häkkeihin). Tarkemmin sanottuna jokainen häkki on laudan ruutujen epätyhjä osajoukko. Jokainen laudan ruutu kuuluu täsmälleen yhteen häkkiin. Häkin ruutujen joukko muodostaa yhtenäisen komponentin: jos kaksi ruutua kuuluu samaan häkkiin, toisesta ruudusta voi aina kulkea toiseen kulkemalla vain kyseisen häkin ruutujen kautta siten, että jokainen askel otetaan kahden sivultaan vierekkäisen ruudun välillä.

Kuva A.1: Lauta, jossa on 6 riviä, 7 saraketta ja 8 häkkiä.

Jokaisessa häkissä pulman laatija kaataa vettä häkin yläreunoista. Painovoiman vuoksi vesi valuu alempana oleviin ruutuihin. Hän kaataa vettä siten, että kaikki alla olevat ehdot täyttyvät:

• Jokainen ruutu on joko kokonaan täynnä vettä tai kokonaan tyhjä.

• Häkki voi olla täynnä vettä, kokonaan tyhjä tai osittain täytetty.

• Jokaisessa häkissä on olemassa jokin vedenkorkeus $\ell$ siten, että kaikki tämän tason alapuolella olevat häkin ruudut ovat täynnä ja kaikki tämän tason yläpuolella olevat häkin ruudut ovat tyhjiä. Toisin sanoen, olkoot $(r_1,c_1)$ ja $(r_2,c_2)$ kaksi saman häkin ruutua siten, että $r_1 \le r_2$; jos ruutu $(r_2,c_2)$ on täynnä, myös ruudun $(r_1,c_1)$ on oltava täynnä.

• Häkkejä käsitellään toisistaan riippumattomina ja erillisinä. Siksi yllä oleva sääntö ei koske eri häkkeihin kuuluvia ruutuja.

Alla on esimerkki kelvollisesta laudasta:

Kuva A.2: Kelvollinen lauta.

Alla on joitakin esimerkkejä epäkelvoista laudoista:

Kuva A.3: Epäkelpo lauta — ruutujen $(5,5)$ ja $(5,7)$ pitäisi olla joko molempien täynnä tai molempien tyhjiä, koska ne ovat samassa häkissä ja samalla rivillä.

Kuva A.4: Epäkelpo lauta — ruudut $(4,2)$, $(4,3)$ ja $(4,4)$ ovat tyhjiä, mutta ne kuuluvat samaan häkkiin kuin vedellä täytetty ruutu $(5,2)$.

Kuva A.5: Epäkelpo lauta — ruudut eivät voi olla vain osittain täytettyjä.

Pulman laatija ei ainoastaan noudata yllä olevia sääntöjä, vaan kiinnittää huomiota myös täytettyjen ruutujen määrään kullakin rivillä. Joillakin riveillä hän haluaa täytettyjen ruutujen määrän olevan yhtä suuri kuin tietyt kiinteät arvot, kun taas muille riveille hän ei aseta mitään rajoituksia.

Tehtäväsi on laskea, kuinka monella tavalla häkkeihin voidaan kaataa vettä siten, että kaikki yllä mainitut säännöt ja vaatimukset täyttyvät. Kahta tapaa pidetään erilaisina jos ja vain jos on olemassa ruutu, joka on toisessa tavassa täynnä ja toisessa tyhjä.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $r,c$ ($1 \le r,c \le 20$). Seuraavat $r+1$ riviä kuvaavat laudan seuraavien sääntöjen mukaisesti:

• Jokainen rivi sisältää täsmälleen $2\cdot c+1$ merkkiä, joista jokainen on jokin seuraavista: välilyönti, alaviiva (_) tai pystyviiva (|).

• Kaikki ensimmäisen ja viimeisen rivin parillisissa indeksipaikoissa olevat merkit ovat alaviivoja, jotka esittävät laudan ylä- ja alareunaa.

• Jokainen syötteen alaviiva, yllä mainittuja lukuun ottamatta, esittää vaakasuoraa häkin rajaa kahden peräkkäisen ruudun välillä samassa sarakkeessa.

• Kaikkien rivien (ensimmäistä lukuun ottamatta) ensimmäinen ja viimeinen merkki ovat pystyviivoja, jotka esittävät laudan vasenta ja oikeaa reunaa.

• Jokainen syötteen pystyviiva, yllä mainittuja lukuun ottamatta, esittää pystysuoraa häkin rajaa kahden peräkkäisen ruudun välillä samalla rivillä.

Katso esimerkkejä asian hahmottamiseksi paremmin.

Määritelmän mukaan:

• Jos sarakkeen kahden peräkkäisen ruudun välillä ei ole vaakasuoraa häkin rajaa, nämä kaksi ruutua kuuluvat samaan häkkiin.

• Jos rivin kahden peräkkäisen ruudun välillä ei ole pystysuoraa häkin rajaa, nämä kaksi ruutua kuuluvat samaan häkkiin.

Viimeinen rivi sisältää $r$ kokonaislukua $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$), jotka kuvaavat kunkin rivin täytettyjen ruutujen määrää koskevat vaatimukset. Jos $x_i=-1$, rivillä $r-i+1$ voi olla mielivaltainen määrä vedellä täytettyjä ruutuja. Muussa tapauksessa tällä rivillä täytettyjen ruutujen määrän on oltava täsmälleen $x_i$.

On taattu, että laudalla on enintään 20 häkkiä.

Tuloste

Tuloste sisältää täsmälleen yhden kokonaisluvun — annetut ehdot täyttävien kelvollisten lautojen lukumäärän modulo $10^9+7$.

Esimerkit

Syöte 1

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

Tuloste 1

1

Huomautus

Ensimmäinen esimerkki vastaa yllä olevaa kuvaa A.2.

Syöte 2

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

Tuloste 2

3

Syöte 3

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

Tuloste 3

1