Vídeojoc P72571

Considereu un vídeojoc en un tauler amb n files i m columnes, amb aquestes regles:

• Inicialment es disposa d’e unitats d’energia, que s’han de gastar del tot.
• Es pot començar a qualsevol casella de la fila de dalt.
• El tauler té obstacles pels quals no es pot passar. No es pot sortir del tauler.
• També hi ha posicions etiquetades amb nombres entre 1 i 9: cada vegada que s’hi passa es gasta el valor de l’etiqueta.
• Es poden fer tres tipus de moviments: Cap avall, sense gastar energia, o horitzontalment cap a la dreta o l’esquerra, gastant una unitat d’energia.
• El joc s’atura immediatament quan s’arriba a qualsevol casella buida de la fila de baix. Es guanya si i només si s’ha gastat exactament tota l’energia.

Donat un tauler, podeu calcular de quantes maneres es pot guanyar?

Entrada

L’entrada consisteix en diversos taulers, cadascun amb n, m i e, seguides d’n files amb m ‍caràcters. Els punts indiquen posicions buides, les ‘X’ obstacles, i els dígits són etiquetes amb el cost de passar per la casella. Suposeu que n i m estan entre 2 i 100, que e està entre 0 i 100, i que a la primera i l’última files no hi ha cap etiqueta.

Sortida

Per a cada tauler, escriviu el nombre de maneres de guanyar, mòdul 10⁸ + 7.