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^8 + 7$.