Escape del laberinto P88921

Haced un programa que calcule el número de caminos diferentes que permiten escapar de un laberinto dado, yendo desde la casilla inferior derecha hasta la casilla superior izquierda. Todos los movimientos deben ser hacia arriba o hacia la izquierda. Hay casillas prohibidas por las que no se puede pasar. Siempre hay por lo menos un camino desde la entrada hasta la salida.

Entrada

La entrada consiste en diversos casos de prueba. Cada caso comienza con el número de filas $n$ y el número de columnas $m$, seguidos de $n$ líneas con $m$ caracteres cada una. Una ‘X’ indica una casilla prohibida, y un punto indica una casilla permitida. Un caso especial con $n = m = 0$ marca el final de la entrada. Podéis asumir $2 \le n \le 40$ y $2 \le m \le 40$.

Salida

Para cada caso, escribid el número de caminos diferentes que van desde la esquina inferior derecha hasta la esquina superior izquierda, y con todos los movimientos hacia arriba o hacia la izquierda. Si ese número fuese mayor o igual que $10^6$, en su lugar hay que escribir “!!!”.

Pista

El hecho que alguna casilla tenga demasiados caminos desde la entrada (o hacia la salida) no implica con certeza que haya demasiados caminos desde la entrada hasta la salida.