Aqua to łamigłówka logiczna na prostokątnej planszy podzielonej na $r$ wierszy i $c$ kolumn. Wiersze są ponumerowane od $1$ do $r$ od dołu do góry, a kolumny od $1$ do $c$ od lewej do prawej. Komórkę w $i$-tym wierszu i $j$-tej kolumnie oznaczamy przez $(i,j)$.

Plansza jest podzielona pionowymi i poziomymi granicami na kilka obszarów spójnych przez wspólne boki. Dokładniej każdy obszar jest niepustym podzbiorem komórek planszy. Każda komórka należy do dokładnie jednego obszaru. Komórki obszaru tworzą składową spójną: między dowolnymi dwiema można przejść wyłącznie przez komórki tego obszaru, w każdym kroku przechodząc między komórkami mającymi wspólny bok.

Rysunek A.1: Plansza o 6 wierszach, 7 kolumnach i 8 obszarach.

Twórca łamigłówki wlewa wodę do każdego obszaru przez jego górne krawędzie. Pod wpływem grawitacji woda opada do niższych komórek. Wlewa ją tak, aby spełnić wszystkie poniższe warunki:

• Każda komórka jest całkowicie wypełniona wodą albo całkowicie pusta.

• Obszar może być całkowicie pełny, całkowicie pusty albo częściowo wypełniony.

• W każdym obszarze istnieje poziom $\ell$, poniżej którego wszystkie komórki są pełne, a powyżej którego wszystkie są puste. Innymi słowy, dla komórek $(r_1,c_1)$ i $(r_2,c_2)$ tego samego obszaru, gdzie $r_1 \le r_2$, jeśli $(r_2,c_2)$ jest pełna, to $(r_1,c_1)$ też musi być pełna.

• Obszary traktuje się osobno i niezależnie. Powyższa reguła nie dotyczy zatem komórek z różnych obszarów.

Poniżej znajduje się przykład poprawnej planszy:

Rysunek A.2: Poprawna plansza.

Poniżej znajdują się przykłady niepoprawnych plansz:

Rysunek A.3: Niepoprawna plansza — komórki $(5,5)$ i $(5,7)$ powinny być obie pełne albo obie puste, ponieważ są w tym samym obszarze i wierszu.

Rysunek A.4: Niepoprawna plansza — komórki $(4,2)$, $(4,3)$ i $(4,4)$ są puste, ale należą do tego samego obszaru co komórka $(5,2)$, która jest pełna wody.

Rysunek A.5: Niepoprawna plansza — komórki nie mogą być częściowo wypełnione.

Twórca łamigłówki przestrzega powyższych zasad i zwraca też uwagę na liczbę pełnych komórek w każdym wierszu. W niektórych wierszach chce, aby ich liczba była równa ustalonej wartości, a na inne wiersze nie nakłada ograniczeń.

Policz sposoby wlania wody do obszarów spełniające wszystkie powyższe zasady i wymagania. Dwa sposoby są różne wtedy i tylko wtedy, gdy istnieje komórka pełna w jednym sposobie, a pusta w drugim.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $r,c$ ($1 \le r,c \le 20$). Kolejne $r+1$ wierszy opisuje planszę według następujących reguł:

• Każdy wiersz zawiera dokładnie $2\cdot c+1$ znaków; każdy jest spacją, podkreśleniem (_) lub pionową kreską (|).

• Wszystkie znaki na parzystych pozycjach indeksu w pierwszym i ostatnim wierszu są podkreśleniami, przedstawiającymi górną i dolną granicę planszy.

• Każde inne podkreślenie oznacza poziomą granicę obszaru między dwiema kolejnymi komórkami w tej samej kolumnie.

• Pierwszy i ostatni znak każdego wiersza oprócz pierwszego jest pionową kreską, oznaczającą lewą i prawą granicę planszy.

• Każda inna pionowa kreska oznacza pionową granicę obszaru między dwiema kolejnymi komórkami w tym samym wierszu.

Dla lepszego zrozumienia zobacz przykłady.

Z definicji:

• Jeśli między dwiema kolejnymi komórkami w kolumnie nie ma poziomej granicy obszaru, należą one do tego samego obszaru.

• Jeśli między dwiema kolejnymi komórkami w wierszu nie ma pionowej granicy obszaru, należą one do tego samego obszaru.

Ostatni wiersz zawiera $r$ liczb całkowitych $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$), określających wymagania dotyczące liczby pełnych komórek w każdym wierszu. Jeśli $x_i=-1$, wiersz $r-i+1$ może mieć dowolną liczbę komórek z wodą. W przeciwnym razie musi mieć dokładnie $x_i$ pełnych komórek.

Gwarantuje się, że plansza ma najwyżej 20 obszarów.

Wyjście

Wypisz dokładnie jedną liczbę całkowitą — liczbę poprawnych plansz spełniających warunki, modulo $10^9+7$.

Przykład

Wejście 1

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

Wyjście 1

1

Uwagi

Pierwszy przykład odpowiada powyższemu rysunkowi A.2.

Wejście 2

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

Wyjście 2

3

Wejście 3

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

Wyjście 3

1