Nombres k-xulos P82361


Statement
 

pdf   zip

thehtml

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 · 104.

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

Pista

No ho recalculeu tot per a cada entrada donada.

Public test cases
  • Input

    5 1
    18 2
    0 3
    12 50000
    

    Output

    10
    99
    981
    31701472
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++