Aqua ist ein logisches Rätselspiel, das auf einem rechteckigen Spielbrett gespielt wird, welches in $r$ Zeilen und $c$ Spalten unterteilt ist. Die Zeilen sind von unten nach oben von $1$ bis $r$ nummeriert, und die Spalten sind von links nach rechts von $1$ bis $c$ nummeriert. Das Feld in der $i$-ten Zeile und der $j$-ten Spalte wird mit $(i,j)$ bezeichnet.

Das Spielbrett ist durch vertikale und horizontale Grenzen in mehrere orthogonal zusammenhängende Gebiete (Käfige) unterteilt. Genauer gesagt ist jeder Käfig eine nichtleere Teilmenge der Felder des Spielbretts. Jedes Feld auf dem Spielbrett gehört zu genau einem Käfig. Die Menge der Felder eines Käfigs bildet eine Zusammenhangskomponente: Wenn zwei Felder zum selben Käfig gehören, ist es immer möglich, von einem Feld zum anderen zu gelangen, indem man nur Felder dieses Käfigs betritt, wobei jeder Schritt zwischen zwei kantenbenachbarten Feldern erfolgt.

Abbildung A.1: Ein Spielbrett mit 6 Zeilen, 7 Spalten und 8 Käfigen.

In jedem Käfig gießt der Rätselersteller Wasser von den oberen Kanten des Käfigs hinein. Aufgrund der Schwerkraft fließt das Wasser in die tiefer gelegenen Felder hinab. Er gießt das Wasser so ein, dass alle folgenden Bedingungen erfüllt sind:

• Jedes Feld ist entweder vollständig mit Wasser gefüllt oder vollständig leer.

• Ein Käfig kann vollständig mit Wasser gefüllt, vollständig leer oder teilweise gefüllt sein.

• In jedem Käfig gibt es einen bestimmten Wasserstand $\ell$, sodass alle Felder des Käfigs unterhalb dieses Wasserstands gefüllt und alle Felder des Käfigs oberhalb dieses Wasserstands leer sind. Mit anderen Worten: Seien $(r_1,c_1)$ und $(r_2,c_2)$ zwei Felder desselben Käfigs mit $r_1 \le r_2$. Wenn das Feld $(r_2,c_2)$ gefüllt ist, muss auch das Feld $(r_1,c_1)$ gefüllt sein.

• Die Käfige werden unabhängig und getrennt voneinander betrachtet. Daher gilt die obige Regel nicht für Felder, die zu verschiedenen Käfigen gehören.

Unten ist ein Beispiel für ein gültiges Spielbrett:

Abbildung A.2: Ein gültiges Spielbrett.

Unten sind einige Beispiele für ungültige Spielbretter:

Abbildung A.3: Ein ungültiges Spielbrett — die Felder $(5,5)$ und $(5,7)$ müssten entweder beide gefüllt oder beide leer sein, da sie sich im selben Käfig und in derselben Zeile befinden.

Abbildung A.4: Ein ungültiges Spielbrett — die Felder $(4,2)$, $(4,3)$ und $(4,4)$ sind leer, gehören aber zum selben Käfig wie das mit Wasser gefüllte Feld $(5,2)$.

Abbildung A.5: Ein ungültiges Spielbrett — Felder können nicht nur teilweise gefüllt sein.

Der Rätselersteller befolgt nicht nur die obigen Regeln, sondern achtet auch auf die Anzahl der gefüllten Felder in jeder Zeile. In einigen Zeilen möchte er, dass die Anzahl der gefüllten Felder bestimmten festen Werten entspricht, während er für andere Zeilen keinerlei Einschränkungen vorgibt.

Deine Aufgabe ist es, die Anzahl der Möglichkeiten zu zählen, Wasser so in die Käfige zu gießen, dass alle oben genannten Regeln und Anforderungen erfüllt sind. Zwei Möglichkeiten gelten genau dann als verschieden, wenn es ein Feld gibt, das in der einen Möglichkeit gefüllt und in der anderen leer ist.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $r,c$ ($1 \le r,c \le 20$). Die nächsten $r+1$ Zeilen beschreiben das Spielbrett nach folgenden Regeln:

• Jede Zeile enthält genau $2\cdot c+1$ Zeichen, wobei jedes Zeichen eines der folgenden ist: Leerzeichen, Unterstrich (_) oder senkrechter Strich (|).

• Alle Zeichen an geraden Indexpositionen in der ersten und der letzten Zeile sind Unterstriche, die den oberen und unteren Rand des Spielbretts darstellen.

• Jeder Unterstrich in der Eingabe, mit Ausnahme der oben genannten, stellt eine horizontale Käfiggrenze zwischen zwei aufeinanderfolgenden Feldern in derselben Spalte dar.

• Das erste und das letzte Zeichen aller Zeilen (außer der ersten) sind senkrechte Striche, die den linken und rechten Rand des Spielbretts darstellen.

• Jeder senkrechte Strich in der Eingabe, mit Ausnahme der oben genannten, stellt eine vertikale Käfiggrenze zwischen zwei aufeinanderfolgenden Feldern in derselben Zeile dar.

Siehe die Beispiele zum besseren Verständnis.

Per Definition gilt:

• Wenn sich zwischen zwei aufeinanderfolgenden Feldern in einer Spalte keine horizontale Käfiggrenze befindet, gehören diese beiden Felder zum selben Käfig.

• Wenn sich zwischen zwei aufeinanderfolgenden Feldern in einer Zeile keine vertikale Käfiggrenze befindet, gehören diese beiden Felder zum selben Käfig.

Die letzte Zeile enthält $r$ ganze Zahlen $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$), welche die Anforderungen an die Anzahl der gefüllten Felder in jeder Zeile beschreiben. Falls $x_i=-1$ ist, kann die ($r-i+1$)-te Zeile eine beliebige Anzahl von mit Wasser gefüllten Feldern aufweisen. Andernfalls muss die Anzahl der gefüllten Felder in dieser Zeile genau $x_i$ betragen.

Es wird garantiert, dass das Spielbrett höchstens 20 Käfige hat.

Ausgabe

Die Ausgabe enthält genau eine ganze Zahl — die Anzahl der gültigen Spielbretter, die die gegebenen Bedingungen erfüllen, modulo $10^9+7$.

Beispiele

Eingabe 1

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

Ausgabe 1

1

Hinweis

Das erste Beispiel entspricht der obigen Abbildung A.2.

Eingabe 2

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

Ausgabe 2

3

Eingabe 3

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

Ausgabe 3

1