== include(page="template/taskheader" task_id="sirgcdx") ==

Poveste şi cerinţă...

_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, dupa aceasta regula:
          a[i]=gcd(b[1],b[2],...b[i])
Funcţia $gcd$ returneaza cel mai mare divizor al parametrilor
De exemplu,şirul $6 3 3$ este şir gcd deoarece este generat de sirul $6 9 24$.
Numaraţi cate şiruri gcd de lungime $N$ exista,având elemente între 1 si $K$,modulo 1.000.000.007.
Remarcaţi că nu contează în cate moduri acestea pot fi generate,conteaza doar cate siruri finale exista.

h2. Date de intrare

Fişierul de intrare $sirgcdx.in$ ...

Fişierul de intrare $sirgcd.in$ conţine pe o singură linie numerele $N$ şi $K$.

h2. Date de ieşire

În fişierul de ieşire $sirgcdx.out$ ...

Fişierul de ieşire $sirgcd.out$ conţine răspunsul, **modulo 1.000.000.007**.

h2. Restricţii

* $... ≤ ... ≤ ...$

*Subtask 1 (5 puncte):* $1<=N,K<=5$
*Subtask 2 (10 puncte):* $1<=N,K<=10^2^$
*Subtask 3 (15 puncte):* $1<=N,K<=10^3^$
*Subtask 4 (20 de puncte):* $1<=N,K<=10^5^$
*Subtask 5 (20 de puncte):* $1<=N<=10^9^,1<=K<=10^5^$
*Subtask 6 (30 de puncte):* $1<=N<=10^9^,1<=K<=10^6^$

h2. Exemplu