Aqua è un rompicapo logico giocato su una griglia rettangolare divisa in $r$ righe e $c$ colonne. Le righe sono numerate da $1$ a $r$ dal basso verso l'alto, e le colonne sono numerate da $1$ a $c$ da sinistra a destra. La cella sulla $i$-esima riga e $j$-esima colonna è indicata con $(i,j)$.
La griglia è suddivisa in diverse regioni ortogonalmente connesse (chiamate gabbie) mediante confini verticali e orizzontali. Più precisamente, ogni gabbia è un sottoinsieme non vuoto delle celle della griglia. Ogni cella della griglia appartiene a esattamente una gabbia. L'insieme delle celle di una gabbia forma una componente connessa: se due celle appartengono alla stessa gabbia, è sempre possibile spostarsi da una cella all'altra passando solo attraverso celle di quella gabbia, in modo che ogni passo sia uno spostamento tra celle adiacenti per lato.
Figura A.1: Una griglia con 6 righe, 7 colonne e 8 gabbie.
In ogni gabbia, il creatore del rompicapo versa dell'acqua dai bordi superiori della gabbia. A causa della gravità, l'acqua cade nelle celle situate a un'altezza inferiore. Egli versa l'acqua in modo da soddisfare tutte le seguenti condizioni:
Ogni cella è completamente piena d'acqua oppure completamente vuota.
Una gabbia può essere piena d'acqua, completamente vuota o parzialmente riempita.
In ogni gabbia esiste un certo livello $\ell$ tale che tutte le celle della gabbia al di sotto di questo livello sono piene e tutte le celle della gabbia al di sopra di questo livello sono vuote. In altre parole, siano $(r_1,c_1)$ e $(r_2,c_2)$ due celle della stessa gabbia tali che $r_1 \le r_2$; se la cella $(r_2,c_2)$ è piena, allora anche la cella $(r_1,c_1)$ deve essere piena.
Le gabbie sono trattate in modo indipendente e separato. Pertanto, la regola precedente non si applica a celle appartenenti a gabbie diverse.
Di seguito è riportato un esempio di griglia valida:
Figura A.2: Una griglia valida.
Di seguito sono riportati alcuni esempi di griglie non valide:
Figura A.3: Una griglia non valida — le celle $(5,5)$ e $(5,7)$ dovrebbero essere entrambe piene o entrambe vuote, poiché si trovano nella stessa gabbia e sulla stessa riga.
Figura A.4: Una griglia non valida — le celle $(4,2)$, $(4,3)$ e $(4,4)$ sono vuote, ma appartengono alla stessa gabbia della cella $(5,2)$, che è piena d'acqua.
Figura A.5: Una griglia non valida — le celle non possono essere riempite solo parzialmente.
Il creatore del rompicapo non solo segue le regole precedenti, ma presta anche attenzione al numero di celle piene su ogni riga. In alcune righe desidera che il numero di celle piene sia uguale a determinati valori fissati, mentre non impone alcuna restrizione sulle altre righe.
Il tuo compito è contare il numero di modi per versare acqua nelle gabbie soddisfacendo tutte le regole e i requisiti sopra indicati. Due modi sono considerati diversi se e solo se esiste una cella che è piena in un modo ma è vuota nell'altro.
Dati di ingresso
La prima riga dei dati di ingresso contiene due interi $r,c$ ($1 \le r,c \le 20$). Le successive $r+1$ righe descrivono la griglia secondo le seguenti regole:
Ogni riga contiene esattamente $2\cdot c+1$ caratteri, ciascuno dei quali è uno dei seguenti: spazio, trattino basso (
_) e barra verticale (|).Tutti i caratteri in posizione di indice pari nella prima riga e nell'ultima riga sono trattini bassi, che rappresentano il bordo superiore e il bordo inferiore della griglia.
Ogni trattino basso nell'ingresso, ad eccezione di quelli menzionati sopra, rappresenta un confine orizzontale di gabbia tra due celle consecutive nella stessa colonna.
Il primo e l'ultimo carattere di tutte le righe (tranne la prima) sono barre verticali, che rappresentano il bordo sinistro e il bordo destro della griglia.
Ogni barra verticale nell'ingresso, ad eccezione di quelle menzionate sopra, rappresenta un confine verticale di gabbia tra due celle consecutive nella stessa riga.
Si vedano gli esempi per una migliore comprensione.
Per definizione:
Se non c'è alcun confine orizzontale di gabbia tra due celle consecutive in una colonna, queste due celle appartengono alla stessa gabbia.
Se non c'è alcun confine verticale di gabbia tra due celle consecutive in una riga, queste due celle appartengono alla stessa gabbia.
L'ultima riga contiene $r$ interi $x_1,x_2,\ldots,x_r$ ($-1 \le x_i \le c$) che descrivono i requisiti riguardanti il numero di celle piene in ciascuna riga. Se $x_i=-1$, la ($r-i+1$)-esima riga può avere un numero arbitrario di celle con acqua. Altrimenti, il numero di celle piene in questa riga deve essere esattamente $x_i$.
È garantito che la griglia ha al massimo 20 gabbie.
Dati di uscita
L'uscita contiene esattamente un intero — il numero di griglie valide che soddisfano le condizioni date, modulo $10^9+7$.
Esempi
Dati di ingresso 1
6 7 _ _ _ _ _ _ _ | | _ _| _ | | | |_ _| |_| | | |_ _ _| _ _| | | _ _| | | | | |_ _| | | |_|_ _ _|_|_ _| 6 3 7 2 2 2
Dati di uscita 1
1
Note
Il primo esempio corrisponde alla Figura A.2 qui sopra.
Dati di ingresso 2
2 3 _ _ _ | | |_ _ _| -1 -1
Dati di uscita 2
3
Dati di ingresso 3
3 3 _ _ _ | _ | | | | | |_|_|_| -1 1 1
Dati di uscita 3
1