_$Dl. IOI$, $Nry$ şi $Semicerc$ s-au săturat de probleme cu enunţuri lungi, care de fapt se dovedesc a fi EZ. Prin urmare, vă vor da un enunţ formal_:
Numim un şir $a$ $şir-gcd$ de lungime $N$ dacă poate fi generat, pe baza unui alt sir b de lungime $N$, după aceasta regula: $a{~i~} = gcd(b{~1~}, b{~2~}, ..., b{~i~})$. Funcţia $gcd$ returnează cel mai mare divizor al parametrilor.

De exemplu, şirul $6 3 3$ este $şir-gcd$ deoarece este generat de şirul $6 9 24$. Număraţi câte $şiruri-gcd$ de lungime $N$ exista, având elemente între $1$ şi $K$, modulo $1.000.000.007$. Remarcaţi că nu contează în câte moduri acestea pot fi generate, contează doar câte şiruri finale exista.

De exemplu, şirul $6 3 3$ este $şir-gcd$ deoarece este generat de şirul $6 9 24$. Număraţi câte $şiruri-gcd$ de lungime $N$ exista, având elemente între $1$ şi $K$, **modulo $1.000.000.007$**. Remarcaţi că nu contează în câte moduri acestea pot fi generate, contează doar câte şiruri finale exista.

h2. Date de intrare