Quants camins? P84609

Considereu una matriu n × m, on a cada casella (i, j) hi ha un nombre x_ij que indica que es pot saltar cap avall a una distància (en nombre de caselles) entre 1 i x_ij, ja sigui verticalment, en diagonal cap a l’esquerra, o en diagonal cap a la dreta. Si anomenem (0, 0) la posició de dalt a l’esquerra, totes les caselles visitades han de tenir coordenades entre 0 i n per a les files (això inclou una fila per sota de l’última), i entre 0 i m − 1 per a les columnes. L’objectiu és començar a la fila 0, i arribar exactament a la fila n. Quants camins hi ha?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, m, i n files amb m naturals. Suposeu que tant n, com m, com els x_ij estan entre 1 i 100.

Sortida

Per a cada cas, escriviu el nombre de camins que comencen a qualsevol casella de la fila de dalt i acaben a qualsevol casella just a sota de la fila de baix, mòdul 10⁹ + 7.