Múltiples de 7 (1) P45672

Calculeu quants nombres amb $n$ dígits són múltiples de 7 i no tenen dígits adjacents repetits. Per senzillesa, els nombres poden començar en 0. Alguns dels dígits poden estar fixats.

Per exemple, amb $n = 2$ n’hi ha 13: 07, 14, …, 70, 84, 91, 98. Però si afegim la restricció que el nombre ha de començar en 7, només n’hi ha un: el 70. (Aquests són els dos primers casos de l’Exemple d’entrada.)

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i el nombre de restriccions $r$. Segueixen $r$ restriccions, cadascuna amb una posició $i$ i un dígit $d$, indicant que a la posició $i$ del nombre hi ha d’haver el dígit $d$. Suposeu $1 \le n \le 30$, $0 \le r \le n$, $0 \le i < n$, $0 \le d \le 9$, i que totes les posicions d’un cas són diferents.

Sortida

Per a cada cas, escriviu la quantitat de nombres que compleixen totes les condicions. Aquest nombre sempre estarà entre 1 i $10^6$.