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 ≤ i < n, 0 ≤ 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⁸ + 7.

Observació

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