Seqüències lletges P84321

En aquest problema, diem que una seqüència de nombres és $k$-lletja si té exactament $k$ parells de posicions adjacents amb dos nombres consecutius. Feu un programa que, donada una $n$, una $k$ i $m$ posicions per a les quals ja s’ha fixat el contingut, compti el nombre de seqüències $k$-lletges de mida $n$ formades amb nombres entre 0 i $n - 1$ i amb el contingut fixat.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i 100, seguida d’una $k$ entre 0 i $n - 1$, seguida d’una $m$ entre 0 i $n$, seguida de $m$ parells $i$ $x$, indicant que a la posició $i$ hi ha d’haver una $x$. Suposeu $0 \le i < n$, $0 \le x < n$, i que totes les $i$ són diferents.

Sortida

Per a cada cas, calculeu quantes seqüències $k$-lletges de mida $n$ formades amb nombres entre 0 i $n - 1$ hi ha amb el contingut fixat, mòdul $10^8 + 7$.

Observació

Es poden obtenir 80 punts sobre 100 si es passen jocs de proves on $n \le 10$.