Dipinti rupestri#10439
Bessie è diventata una pittrice e dipinge quadri di caverne! In questo momento sta lavorando a un quadro che rappresenta una griglia di altezza , in cui ogni riga contiene esattamente celle. Ogni cella è vuota, oppure riempita di roccia, oppure riempita d'acqua. Bessie ha già colorato tutte le celle che contengono roccia, incluso l'intero bordo del quadro. Ora vuole riempire d'acqua alcune celle vuote in modo tale che, se il quadro fosse una vera caverna, non si verificherebbe alcun movimento complessivo dell'acqua.
Definiamo l'altezza di una cella che si trova nella -esima riga dall'alto come n + 1 - i. Bessie vuole che il suo quadro soddisfi la seguente condizione:
Supponiamo che la cella sia riempita d'acqua. Se esiste un percorso dalla cella alla cella che passa solo attraverso celle vuote o celle riempite d'acqua la cui altezza non supera l'altezza della cella , e ogni due celle adiacenti del percorso hanno un lato in comune, allora anche la cella deve essere riempita d'acqua.
Trova il numero di quadri distinti che Bessie può creare, modulo 10^9 + 7. Bessie può riempire d'acqua un numero qualsiasi di celle vuote, incluso nessuna oppure tutte.
La prima riga contiene due numeri interi e m~(1 \le n, m \le 1000).
Ciascuna delle successive righe contiene caratteri. Ogni carattere è '' oppure '#', che indicano rispettivamente una cella vuota e una cella riempita di roccia. La prima e l'ultima riga, così come la prima e l'ultima colonna, sono composte esclusivamente da caratteri '#'.
Stampa un singolo numero intero: il numero di quadri che soddisfano la condizione, modulo 10^9 + 7.
Se una qualsiasi cella nella seconda riga è riempita d'acqua, allora anche tutte le celle vuote devono essere riempite d'acqua. Altrimenti, supponiamo che nessuna cella nella seconda riga sia riempita d'acqua. Allora Bessie può scegliere indipendentemente se riempire d'acqua o no ciascuna delle tre regioni orizzontalmente connesse di celle vuote nella terza riga. Pertanto, il numero totale di quadri è 1 + 2^3 = 9.
Esempio 1