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 ≤ n ≤ 30, 0 ≤ r ≤ n, 0 ≤ i < n, 0 ≤ d ≤ 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⁶.