Aqua est un jeu de réflexion logique qui se joue sur une grille rectangulaire divisée en $r$ lignes et $c$ colonnes. Les lignes sont numérotées de $1$ à $r$ de bas en haut, et les colonnes sont numérotées de $1$ à $c$ de gauche à droite. La case située à la $i$-ème ligne et à la $j$-ème colonne est notée $(i,j)$.

La grille est divisée en plusieurs régions orthogonalement connexes (appelées cages) à l'aide de frontières verticales et horizontales. Plus précisément, chaque cage est un sous-ensemble non vide de cases de la grille. Chaque case de la grille appartient à exactement une cage. L'ensemble des cases d'une cage forme une composante connexe : si deux cases appartiennent à la même cage, il est toujours possible de se déplacer de l'une à l'autre en ne passant que par des cases de cette cage, chaque pas se faisant entre deux cases adjacentes par un côté.

Figure A.1 : Une grille avec 6 lignes, 7 colonnes et 8 cages.

Dans chaque cage, le créateur du puzzle verse de l'eau depuis les bords supérieurs de la cage. Sous l'effet de la gravité, l'eau tombe dans les cases situées à une hauteur inférieure. Il verse l'eau de manière à satisfaire toutes les conditions ci-dessous :

• Chaque case est soit complètement remplie d'eau, soit complètement vide.

• Une cage peut être pleine d'eau, complètement vide ou partiellement remplie.

• Dans chaque cage, il existe un certain niveau $\ell$ tel que toutes les cases de la cage situées sous ce niveau soient remplies, et toutes les cases de la cage situées au-dessus de ce niveau soient vides. Autrement dit, soient $(r_1,c_1)$ et $(r_2,c_2)$ deux cases d'une même cage telles que $r_1 \le r_2$ ; si la case $(r_2,c_2)$ est remplie, alors la case $(r_1,c_1)$ doit également être remplie.

• Les cages sont traitées de manière indépendante et séparée. Par conséquent, la règle ci-dessus ne s'applique pas aux cases appartenant à des cages différentes.

Voici un exemple de grille valide :

Figure A.2 : Une grille valide.

Voici quelques exemples de grilles invalides :

Figure A.3 : Une grille invalide — les cases $(5,5)$ et $(5,7)$ devraient être soit toutes les deux remplies, soit toutes les deux vides, car elles sont dans la même cage et sur la même ligne.

Figure A.4 : Une grille invalide — les cases $(4,2)$, $(4,3)$ et $(4,4)$ sont vides, mais elles appartiennent à la même cage que la case $(5,2)$, qui est remplie d'eau.

Figure A.5 : Une grille invalide — les cases ne peuvent pas être partiellement remplies.

Le créateur du puzzle ne se contente pas de suivre les règles ci-dessus, il prête également attention au nombre de cases remplies sur chaque ligne. Dans certaines lignes, il souhaite que le nombre de cases remplies soit égal à des valeurs fixées, tout en n'imposant aucune restriction sur les autres lignes.

Votre tâche consiste à compter le nombre de façons de verser de l'eau dans les cages tout en respectant toutes les règles et exigences ci-dessus. Deux façons sont considérées comme différentes si et seulement s'il existe une case qui est remplie dans l'une mais vide dans l'autre.

Entrée

La première ligne de l'entrée contient deux entiers $r,c$ ($1 \le r,c \le 20$). Les $r+1$ lignes suivantes décrivent la grille selon les règles suivantes :

• Chaque ligne contient exactement $2\cdot c+1$ caractères, chacun étant l'un des suivants : un espace, un tiret bas (_) ou une barre verticale (|).

• Tous les caractères situés aux positions d'indice pair sur la première ligne et la dernière ligne sont des tirets bas, représentant les bords supérieur et inférieur de la grille.

• Chaque tiret bas de l'entrée, à l'exception de ceux mentionnés ci-dessus, représente une frontière horizontale de cage entre deux cases consécutives d'une même colonne.

• Le premier et le dernier caractère de toutes les lignes (sauf la première) sont des barres verticales, représentant les bords gauche et droit de la grille.

• Chaque barre verticale de l'entrée, à l'exception de celles mentionnées ci-dessus, représente une frontière verticale de cage entre deux cases consécutives d'une même ligne.

Consultez les exemples pour une meilleure compréhension.

Par définition :

• S'il n'y a aucune frontière horizontale de cage entre deux cases consécutives d'une colonne, ces deux cases appartiennent à la même cage.

• S'il n'y a aucune frontière verticale de cage entre deux cases consécutives d'une ligne, ces deux cases appartiennent à la même cage.

La dernière ligne contient $r$ entiers $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) décrivant les exigences relatives au nombre de cases remplies dans chaque ligne. Si $x_i=-1$, la ($r-i+1$)-ième ligne peut contenir un nombre quelconque de cases remplies d'eau. Sinon, le nombre de cases remplies dans cette ligne doit être exactement égal à $x_i$.

Il est garanti que la grille comporte au plus 20 cages.

Sortie

La sortie contient exactement un entier — le nombre de grilles valides satisfaisant les conditions données, modulo $10^9+7$.

Exemples

Entrée 1

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

Sortie 1

1

Note

Le premier exemple correspond à la figure A.2 ci-dessus.

Entrée 2

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

Sortie 2

3

Entrée 3

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

Sortie 3

1