Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-06-13 17:46:22.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sirgcdx.in, sirgcdx.outSursăJunior Challenge 2018
AutorBogdan PopAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test0.75 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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, după aceasta regula: ai = gcd(b1, b2, ..., bi). Funcţia gcd returnează cel mai mare divizor al parametrilor.

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.

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 ≤ 102
  • Subtask 3 - 15 puncte: 1 ≤ N, K ≤ 103
  • Subtask 4 - 20 de puncte: 1 ≤ N, K ≤ 105
  • Subtask 5 - 20 de puncte: 1 ≤ N ≤ 109, 1 ≤ K ≤ 105
  • Subtask 6 - 30 de puncte: 1 ≤ N ≤ 109, 1 ≤ K ≤ 106
  • Cine nu e cuminte şi întreabă de unde vine 'x'-ul din titlu e posibil să nu mai primească 100 de puncte.

Exemplu

sirgcdx.insirgcdx.out
3 24
31 1772262
111 112787881353

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?