Bombetes en un tauler P40953

Considereu un tauler amb $n \times m$ bombetes. Algunes han d’estan apagades, algunes enceses, i d’algunes se’n pot escollir l’estat. A més, sabem quantes bombetes exactament han d’estar enceses a cada fila i a cada columna. Feu un programa per comptar totes les combinacions coherents amb les restriccions donades.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $m$. Segueixen $n$ files amb $m$ caràcters cadascuna. Una ‘X’ indica una bombeta que ha d’estar apagada, una ‘O’ una bombeta que ha d’estar encesa, i un punt una bombeta de la qual es pot triar l’estat. Segueixen els $n$ comptadors de bombetes enceses a cada fila, i els $m$ comptadors de bombetes enceses a cada columna. Podeu suposar $1 \le n \cdot m \le 100$.

Sortida

Per a cada tauler, escriviu de quantes maneres es poden complir totes les restriccions. Amb els jocs de proves donats, aquest nombre sempre estarà entre 1 i $10^6$.