_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 ])$

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