== include(page="template/taskheader" task_id="sirgcdx") ==
_$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.

Numim un şir $a$ $şir-gcd$ de lungime $N$ dacă poate fi generat, pe baza unui alt şir b de lungime $N$, după această regulă: $a{~i~} = gcd(b{~1~}, b{~2~}, ..., b{~i~})$. Funcţia $gcd$ returnează cel mai mare divizor al parametriilor.

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$ există, 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

h3. Explicaţie
Pentru primul exemplu,şirurile sunt: $(2,2,2)$ , $(2,2,1)$ , $(2,1,1)$ , $(1,1,1)$ .

Primul sir poate fi generat pe baza şirului $(2,2,2)$, al doilea de şirul $(2,2,1)$, al treilea de şirul $(2,1,2)$, al patrulea de şirul $(1,2,2)$.

Primul şir poate fi generat pe baza şirului $(2,2,2)$, al doilea de şirul $(2,2,1)$, al treilea de şirul $(2,1,2)$, al patrulea de şirul $(1,2,2)$.

Observaţi că există şi alte şiruri care pot genera unele din aceste şiruri (de exemplu $(1,1,1)$ poate fi generat şi de şirul $(1,2,1)$).
== include(page="template/taskfooter" task_id="sirgcdx") ==