Caminar i saltar P87501

Donat un mapa n × m amb obstacles, de quantes maneres es pot anar des de la casella superior esquerra fins a la casella inferior dreta? Només es pot caminar (moure’s a la casella immediatament a la dreta o avall), o saltar (moure’s a la casella dues posicions a la dreta o avall, però només si enmig hi ha un obstacle). No es pot passar mai per cap obstacle.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits de n files amb m caràcters. Les posicions ocupades tenen una ‘X’, i les buides un punt. Les caselles inicial i final sempre estan buides. Podeu suposar que tant n com m estan entre 2 i 100.

Sortida

Per a cada cas, escriviu el nombre de maneres diferents d’anar des de l’inici fins al final, segons s’ha explicat anteriorment. Com que aquest nombre pot ser molt gros, feu els càlculs mòdul 10⁸ + 7.