Número de caminos P30076

Considerad un tablero $n \times m$ con $p$ casillas prohibidas. Os encontráis en la casilla $(1, 1)$, que corresponde a la esquina superior izquierda, y debéis ir a la casilla $(n, m)$, que corresponde a la esquina inferior derecha. Sólo podéis hacer movimientos hacia la derecha y hacia abajo, y no podéis pasar por las casillas prohibidas. ¿Cuántos caminos existen?

Entrada

La entrada consiste en diversos casos, cada uno con $n$, $m$ y $p$, seguidas de los $p$ pares de coordenadas de las casillas prohibidas, todas diferentes. Suponed $n \ge 1$, $m \ge 1$, y que la casilla inicial y la final son diferentes y no están prohibidas.

Salida

Para cada caso, escribid el número de caminos válidos módulo $10^9 + 7$.

Puntuación

• test-1:   Entradas donde $n \le 5$, $m \le 5$ y $p = 0$, como el Ejemplo 1.

• test-2:   Entradas donde $n \le 1000$, $m \le 1000$ y $p = 0$, como el Ejemplo 2.

• test-3:   Entradas donde $n \le 30$, $m \le 30$ y $p \le 10$, como el Ejemplo 3.

• test-4:   Entradas donde $n \le 1000$, $m \le 1000$ y $p \le 10$, como el Ejemplo 4.

Pista

Los juegos de pruebas privados tienen muchos casos, y la solución esperada resuelve cada uno básicamente en coste $\Theta(p^2)$.