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 ≤ k ≤ 18 i 1 ≤ n ≤ 5 · 10⁴.

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⁸ + 7.

Pista

No ho recalculeu tot per a cada entrada donada.