== 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, 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.
_$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 ş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$ 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^$
* Cine întreabă de unde vine 'x'-ul din titlu nu mai primeşte 100 de puncte
* $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
table(example). |_. sirgcdx.in |_. sirgcdx.out |
| 3 2
| 4
|
| 3 2 | 4 |
| 31 17 | 72262 |
| 111 112 | 787881353 |
h3. Explicaţie
Pentry primul exemplu,şirurile sunt: $(2,2,2)$ , $(2,2,1)$ , $(2,1,1)$ , $(1,1,1)$ .
Pentru primul exemplu,şirurile sunt: $(2,2,2)$ , $(2,2,1)$ , $(2,1,1)$ , $(1,1,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") ==
