Secuencias feas P84321

En este problema, decimos que una secuencia de números es $k$-fea si tiene exactamente $k$ pares de posiciones adyacentes con dos números consecutivos. Haced un programa que, dada una $n$, una $k$ y $m$ posiciones para las cuales ya se ha fijado el contenido, cuente el número de secuencias $k$-feas de tamaño $n$ formadas con números entre 0 y $n - 1$ y con el contenido fijado.

Entrada

La entrada consiste en diversos casos, cada uno con una $n$ entre 1 y 100, seguida de una $k$ entre 0 y $n - 1$, seguida de una $m$ entre 0 y $n$, seguida de $m$ pares $i$ $x$, indicando que en la posición $i$ tiene que haber una $x$. Suponed $0 \le y < n$, $0 \le x < n$, y que todas las $i$ son diferentes.

Salida

Para cada caso, calculad cuantas secuencias $k$-feas de tamaño $n$ formadas con números entre 0 y $n - 1$ hay con el contenido fijado, módulo $10^8 + 7$.

Observación

Se pueden obtener 80 puntos sobre 100 si se pasan juegos de pruebas donde $n \le 10$.