Quants camins? P84609

Considereu una matriu $n \times 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^9 + 7$.