Aqua es un juego de lógica en un tablero rectangular dividido en $r$ filas y $c$ columnas. Las filas se numeran del $1$ al $r$ de abajo arriba, y las columnas del $1$ al $c$ de izquierda a derecha. La celda de la fila $i$ y la columna $j$ se denota por $(i,j)$.

El tablero se divide mediante límites verticales y horizontales en varias regiones conectadas ortogonalmente. Más precisamente, cada región es un subconjunto no vacío de las celdas. Cada celda pertenece exactamente a una región. Las celdas de una región forman una componente conexa: entre dos celdas de la misma región siempre se puede pasar usando solo celdas de esa región, con cada paso entre celdas que comparten un lado.

Figura A.1: Un tablero de 6 filas, 7 columnas y 8 regiones.

En cada región, el creador vierte agua desde sus bordes superiores. Debido a la gravedad, el agua cae a las celdas más bajas. Vierte el agua de modo que se cumplan todas estas condiciones:

• Cada celda está completamente llena de agua o completamente vacía.

• Una región puede estar llena de agua, completamente vacía o parcialmente llena.

• En cada región existe un nivel $\ell$ tal que todas las celdas de la región por debajo están llenas y todas las celdas por encima están vacías. Es decir, sean $(r_1,c_1)$ y $(r_2,c_2)$ dos celdas de la misma región con $r_1 \le r_2$; si $(r_2,c_2)$ está llena, $(r_1,c_1)$ también debe estar llena.

• Las regiones se tratan por separado e independientemente. Por tanto, la regla anterior no se aplica a celdas de regiones distintas.

A continuación se muestra un ejemplo de tablero válido:

Figura A.2: Un tablero válido.

A continuación se muestran algunos tableros no válidos:

Figura A.3: Tablero no válido: las celdas $(5,5)$ y $(5,7)$ deben estar ambas llenas o ambas vacías, porque pertenecen a la misma región y fila.

Figura A.4: Tablero no válido: las celdas $(4,2)$, $(4,3)$ y $(4,4)$ están vacías, pero pertenecen a la misma región que $(5,2)$, que está llena de agua.

Figura A.5: Tablero no válido: las celdas no pueden estar parcialmente llenas.

El creador no solo sigue estas reglas; también tiene en cuenta el número de celdas llenas de cada fila. En algunas filas quiere que este número sea igual a ciertos valores fijos, mientras que no impone restricciones a otras filas.

Tu tarea es contar las formas de verter agua en las regiones que satisfagan todas las reglas y requisitos anteriores. Dos formas se consideran diferentes si y solo si existe una celda llena en una y vacía en la otra.

Entrada

La primera línea contiene dos enteros $r,c$ ($1 \le r,c \le 20$). Las siguientes $r+1$ líneas describen el tablero según estas reglas:

• Cada línea contiene exactamente $2\cdot c+1$ caracteres, cada uno de los cuales es un espacio, un guion bajo (_) o una barra vertical (|).

• Todos los caracteres en posiciones de índice par de la primera y la última línea son guiones bajos, que representan los bordes superior e inferior del tablero.

• Cada guion bajo restante representa un límite horizontal entre regiones situado entre dos celdas consecutivas de la misma columna.

• El primer y último carácter de todas las líneas salvo la primera son barras verticales, que representan los bordes izquierdo y derecho del tablero.

• Cada barra vertical restante representa un límite vertical entre regiones situado entre dos celdas consecutivas de la misma fila.

Consulta los ejemplos para comprenderlo mejor.

Por definición:

• Si no hay un límite horizontal entre dos celdas consecutivas de una columna, pertenecen a la misma región.

• Si no hay un límite vertical entre dos celdas consecutivas de una fila, pertenecen a la misma región.

La última línea contiene $r$ enteros $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) que describen los requisitos del número de celdas llenas de cada fila. Si $x_i=-1$, la fila $r-i+1$ puede tener cualquier número de celdas con agua. En otro caso, el número de celdas llenas de esa fila debe ser exactamente $x_i$.

Se garantiza que el tablero tiene como máximo 20 regiones.

Salida

La salida contiene exactamente un entero: el número de tableros válidos que cumplen las condiciones, módulo $10^9+7$.

Ejemplos

Entrada 1

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

Salida 1

1

Nota

El primer ejemplo corresponde a la figura A.2 de arriba.

Entrada 2

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

Salida 2

3

Entrada 3

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

Salida 3

1