Múltiples de 7 (2) P43075

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.

Per exemple, amb $n = 1$ n’hi ha 2: 0 i 7. I amb $n = 2$ n’hi ha 13: 07, 14, …, 70, 84, 91, 98. (Aquests són els dos primers casos de l’Exemple d’entrada.)

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $n$ entre 1 i $10^4$.

Sortida

Per a cada $n$, escriviu la quantitat demanada mòdul $10^8 + 7$.