== 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

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

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

h2. Date de ieşire

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

Fişierul de ieşire $sirgcdx.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^$

* $Subtask 1 (testul 1) - 5 puncte (testul 1): 1 ≤ N, K ≤ 5$
* $Subtask 2 (testele 2 - 3) - 10 puncte (testele 2 şi 3): 1 ≤ N, K ≤ 10^2^$
* $Subtask 3 (testele 4 - 6) - 15 puncte (testele 4-6): 1 ≤ N, K ≤ 10^3^$
* $Subtask 4 (testele 7 - 10) - 20 de puncte (testele 7-10): 1 ≤ N, K ≤ 10^5^$
* $Subtask 5 (testele 11 - 14) - 20 de puncte (testele 11-14): 1 ≤ N ≤ 10^9^, 1 ≤ K ≤ 10^5^$
* $Subtask 6 (testele 15 - 20) - 30 de puncte (testele 15-20): 1 ≤ N ≤ 10^9^, 1 ≤ K ≤ 10^6^$

* Cine nu e cuminte şi întreabă de unde vine 'x'-ul din titlu e posibil să nu mai primească $100$ de puncte.
h2. Exemplu

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)$.
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)$).

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 dintre aceste şiruri (de exemplu $(1,1,1)$ poate fi generat şi de şirul $(1,2,1)$).

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