Aqua er et logisk puslespill som spilles på et rektangulært brett delt inn i $r$ rader og $c$ kolonner. Radene er nummerert fra $1$ til $r$ nedenfra og opp, og kolonnene er nummerert fra $1$ til $c$ fra venstre mot høyre. Ruten på den $i$-te raden og den $j$-te kolonnen betegnes som $(i,j)$.

Brettet er delt inn i flere ortogonalt sammenhengende områder (bur) ved hjelp av vertikale og horisontale grenser. Mer presist er hvert bur en ikke-tom delmengde av brettets ruter. Hver rute på brettet tilhører nøyaktig ett bur. Mengden av ruter i et bur danner en sammenhengende komponent: Hvis to ruter tilhører samme bur, er det alltid mulig å flytte seg fra den ene ruten til den andre ved kun å gå gjennom ruter i dette buret, slik at hvert steg er en forflytning mellom to ruter som deler en sidekant.

Figur A.1: Et brett med 6 rader, 7 kolonner og 8 bur.

I hvert bur heller puslespillskaperen vann fra de øvre kantene av buret. På grunn av tyngdekraften renner vannet ned til rutene i lavere høyde. Han heller vann slik at alle betingelsene nedenfor er oppfylt:

• Hver rute er enten helt fylt med vann eller helt tom.

• Et bur kan være helt fylt med vann, helt tomt eller delvis fylt.

• I hvert bur finnes det et visst vannivå $\ell$ slik at alle ruter i buret under dette nivået er fylt, og alle ruter i buret over dette nivået er tomme. Med andre ord, la $(r_1,c_1)$ og $(r_2,c_2)$ være to ruter i samme bur slik at $r_1 \le r_2$; hvis ruten $(r_2,c_2)$ er fylt, må også ruten $(r_1,c_1)$ være fylt.

• Burene behandles uavhengig og adskilt fra hverandre. Derfor gjelder ikke regelen ovenfor for ruter som tilhører forskjellige bur.

Nedenfor er et eksempel på et gyldig brett:

Figur A.2: Et gyldig brett.

Nedenfor er noen eksempler på ugyldige brett:

Figur A.3: Et ugyldig brett — rutene $(5,5)$ og $(5,7)$ burde enten begge være fylt eller begge være tomme, siden de er i samme bur og på samme rad.

Figur A.4: Et ugyldig brett — rutene $(4,2)$, $(4,3)$ og $(4,4)$ er tomme, men de er i samme bur som ruten $(5,2)$, som er fylt med vann.

Figur A.5: Et ugyldig brett — ruter kan ikke være bare delvis fylt.

Puslespillskaperen følger ikke bare reglene ovenfor, han legger også merke til antallet fylte ruter på hver rad. På noen rader ønsker han at antallet fylte ruter skal være lik bestemte faste verdier, mens han ikke legger noen begrensninger på andre rader.

Din oppgave er å telle antall måter å helle vann i burene på som tilfredsstiller alle reglene og kravene ovenfor. To måter regnes som forskjellige hvis og bare hvis det finnes en rute som er fylt på den ene måten, men tom på den andre.

Inndata

Den første linjen i inndataene inneholder to heltall $r,c$ ($1 \le r,c \le 20$). De neste $r+1$ linjene beskriver brettet etter følgende regler:

• Hver linje inneholder nøyaktig $2\cdot c+1$ tegn, der hvert tegn er ett av følgende: mellomrom, understrek (_) eller vertikal strek (|).

• Alle tegn på partallsindekser på den første og den siste linjen er understreker, som viser den øvre og den nedre kanten av brettet.

• Hver understrek i inndataene, bortsett fra de som er nevnt ovenfor, representerer en horisontal burgrense mellom to påfølgende ruter i samme kolonne.

• Det første og det siste tegnet på alle linjer (unntatt den første) er vertikale streker, som viser den venstre og den høyre kanten av brettet.

• Hver vertikal strek i inndataene, bortsett fra de som er nevnt ovenfor, representerer en vertikal burgrense mellom to påfølgende ruter på samme rad.

Se eksemplene for bedre forståelse.

Per definisjon:

• Hvis det ikke er noen horisontal burgrense mellom to påfølgende ruter i en kolonne, tilhører disse to rutene samme bur.

• Hvis det ikke er noen vertikal burgrense mellom to påfølgende ruter på en rad, tilhører disse to rutene samme bur.

Den siste linjen inneholder $r$ heltall $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) som beskriver kravene til antall fylte ruter på hver rad. Hvis $x_i=-1$, kan den ($r-i+1$)-te raden ha et vilkårlig antall ruter med vann. Ellers må antallet fylte ruter på denne raden være nøyaktig $x_i$.

Det er garantert at brettet har høyst 20 bur.

Utdata

Utdataene skal inneholde nøyaktig ett heltall — antallet gyldige brett som tilfredsstiller de gitte betingelsene, modulo $10^9+7$.

Eksempler

Inndata 1

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

Utdata 1

1

Forklaring

Det første eksempelet tilsvarer figur A.2 ovenfor.

Inndata 2

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

Utdata 2

3

Inndata 3

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

Utdata 3

1