Nombres k-xulos P82361

En aquest problema, direm que un nombre és $k$-xulo si no té cap parell de dígits consecutius que sumin $k$.

Donada una $k$ i una $n$, podeu calcular quants nombres $k$-xulos d’$n$ dígits hi ha? Tingueu en compte que els nombres poden començar en un o més zeros.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una $k$ i una $n$. Suposeu $0 \le k \le 18$ i $1 \le n \le 5 \cdot 10^4$.

Sortida

Per a cada cas, escriviu la quantitat de nombres $k$-xulos d’$n$ dígits. Com que el resultat podria ser molt gran, feu els càlculs mòdul $10^8 + 7$.

Pista

No ho recalculeu tot per a cada entrada donada.