Fişierul intrare/ieşire:sirgcdx.in, sirgcdx.outSursăJunior Challenge 2018
AutorBogdan PopAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test1.5 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 şir b de lungime N, după această regulă: ai = gcd(b1, b2, ..., bi). 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.

Date de intrare

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

Date de ieşire

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

Restricţii

  • 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 ≤ 102
  • Subtask 3 (testele 4 - 6) - 15 puncte (testele 4-6): 1 ≤ N, K ≤ 103
  • Subtask 4 (testele 7 - 10) - 20 de puncte (testele 7-10): 1 ≤ N, K ≤ 105
  • Subtask 5 (testele 11 - 14) - 20 de puncte (testele 11-14): 1 ≤ N ≤ 109, 1 ≤ K ≤ 105
  • Subtask 6 (testele 15 - 20) - 30 de puncte (testele 15-20): 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 ş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)).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?