Fişierul intrare/ieşire:	sirgcdx.in, sirgcdx.out	Sursă	Junior Challenge 2018
Autor	Bogdan Pop	Adăugată de	Junior Challenge •JuniorChallenge2018
Timp execuţie pe test	0.75 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

Date de intrare

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

Date de ieşire

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

Restricţii

• Subtask 1 (5 puncte): 1<=N,K<=5
• Subtask 2 (10 puncte): 1<=N,K<=10²
• Subtask 3 (15 puncte): 1<=N,K<=10³
• Subtask 4 (20 de puncte): 1<=N,K<=10⁵
• Subtask 5 (20 de puncte): 1<=N<=10⁹,1<=K<=10⁵
• Subtask 6 (30 de puncte): 1<=N<=10⁹,1<=K<=10⁶
• Cine nu e cuminte şi întreabă de unde vine 'x'-ul din titlu e posibil să nu mai primească 100 de puncte.

Exemplu

Explicaţie

Pentry primul exemplu,şirurile sunt: (2,2,2) , (2,2,1) , (2,1,1) , (1,1,1) .

Cum se trimit solutii?