Aqua är ett logiskt pusselspel som spelas på ett rektangulärt bräde uppdelat i $r$ rader och $c$ kolumner. Raderna är numrerade från $1$ till $r$ nerifrån och upp, och kolumnerna är numrerade från $1$ till $c$ från vänster till höger. Rutan på den $i$:te raden och den $j$:te kolumnen betecknas med $(i,j)$.

Brädet är uppdelat i flera ortogonalt sammanhängande områden (burar) med hjälp av vertikala och horisontella gränser. Mer precist är varje bur en icke-tom delmängd av brädets rutor. Varje ruta på brädet tillhör exakt en bur. Mängden rutor i en bur bildar en sammanhängande komponent: om två rutor tillhör samma bur är det alltid möjligt att förflytta sig från den ena rutan till den andra genom att endast passera rutor i denna bur, så att varje steg sker mellan två rutor som delar en sida.

Figur A.1: Ett bräde med 6 rader, 7 kolumner och 8 burar.

I varje bur häller pusselskaparen vatten från burens övre kanter. På grund av tyngdkraften rinner vattnet ner till rutor på lägre höjd. Han häller vatten så att alla nedanstående villkor är uppfyllda:

• Varje ruta är antingen helt fylld med vatten eller helt tom.

• En bur kan vara helt fylld med vatten, helt tom eller delvis fylld.

• I varje bur finns det en viss vattennivå $\ell$ sådan att alla rutor i buren under denna nivå är fyllda, och alla rutor i buren ovanför denna nivå är tomma. Med andra ord, låt $(r_1,c_1)$ och $(r_2,c_2)$ vara två rutor i samma bur sådana att $r_1 \le r_2$; om rutan $(r_2,c_2)$ är fylld måste även rutan $(r_1,c_1)$ vara fylld.

• Burarna behandlas oberoende och separat från varandra. Därför gäller inte regeln ovan för rutor som tillhör olika burar.

Nedan visas ett exempel på ett giltigt bräde:

Figur A.2: Ett giltigt bräde.

Nedan visas några exempel på ogiltiga bräden:

Figur A.3: Ett ogiltigt bräde — rutorna $(5,5)$ och $(5,7)$ borde antingen båda vara fyllda eller båda vara tomma, eftersom de ligger i samma bur och på samma rad.

Figur A.4: Ett ogiltigt bräde — rutorna $(4,2)$, $(4,3)$ och $(4,4)$ är tomma, men de tillhör samma bur som rutan $(5,2)$, vilken är fylld med vatten.

Figur A.5: Ett ogiltigt bräde — rutor kan inte vara endast delvis fyllda.

Pusselskaparen följer inte bara reglerna ovan, utan fäster också vikt vid antalet fyllda rutor på varje rad. På vissa rader vill han att antalet fyllda rutor ska vara lika med givna fasta värden, medan han inte sätter några begränsningar alls på andra rader.

Din uppgift är att räkna antalet sätt att hälla vatten i burarna så att alla ovanstående regler och krav uppfylls. Två sätt betraktas som olika om och endast om det finns en ruta som är fylld på det ena sättet men tom på det andra.

Indata

Den första raden i indatan innehåller två heltal $r,c$ ($1 \le r,c \le 20$). De följande $r+1$ raderna beskriver brädet enligt följande regler:

• Varje rad innehåller exakt $2\cdot c+1$ tecken, där varje tecken är ett av följande: mellanslag, understreck (_) eller vertikalstreck (|).

• Alla tecken på jämna indexpositioner på den första och den sista raden är understreck, vilka representerar brädets övre och undre kant.

• Varje understreck i indatan, förutom de som nämnts ovan, representerar en horisontell burgräns mellan två på varandra följande rutor i samma kolumn.

• Det första och det sista tecknet på alla rader (förutom den första) är vertikalstreck, vilka representerar brädets vänstra och högra kant.

• Varje vertikalstreck i indatan, förutom de som nämnts ovan, representerar en vertikal burgräns mellan två på varandra följande rutor på samma rad.

Se exemplen för bättre förståelse.

Per definition:

• Om det inte finns någon horisontell burgräns mellan två på varandra följande rutor i en kolumn, tillhör dessa två rutor samma bur.

• Om det inte finns någon vertikal burgräns mellan två på varandra följande rutor på en rad, tillhör dessa två rutor samma bur.

Den sista raden innehåller $r$ heltal $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) som beskriver kraven på antalet fyllda rutor på varje rad. Om $x_i=-1$ kan den ($r-i+1$):te raden ha ett godtyckligt antal rutor med vatten. Annars måste antalet fyllda rutor på denna rad vara exakt $x_i$.

Det garanteras att brädet har högst 20 burar.

Utdata

Utdatan ska innehålla exakt ett heltal — antalet giltiga bräden som uppfyller de givna villkoren, modulo $10^9+7$.

Exempel

Indata 1

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

Utdata 1

1

Förklaring

Det första exemplet motsvarar figur A.2 ovan.

Indata 2

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

Utdata 2

3

Indata 3

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

Utdata 3

1