Fişierul intrare/ieşire:	nkl.in, nkl.out	Sursă	Grigore Moisil 2018, 10
Autor	Vlad Mihaly	Adăugată de	Grigore Moisil •grigore.moisil
Timp execuţie pe test	0.15 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Nkl

Se dă un număr natural nenul N. O secvenţă de K numere naturale nenule (a1,a2,…,ak) se numeşte L-perfectă dacă cel mai mic multiplu comun a oricăror L numere din secvenţa (a1,a2,…,ak) este N. Se cere să se determine numărul secvenţelor ordonate de K numere care sunt L-perfecte.

Date de intrare

Fişierul nkl.in conţine pe prima linie un număr natural N cu semnificaţia de mai sus, pe a doua linie un număr natural nenul Q, iar pe următoarele Q linii câte două numere K şi L separate printr-un spaţiu, cu semnificaţia din enunţ.

Date de ieşire

Fişierul nkl.out conţine Q linii, corespunzătoare celor Q perechi de numere K şi L. Pentru fiecare pereche se va afişa numărul secvenţelor ordonate de dimensiune K care sunt L-perfecte modulo 10⁹ + 7.

Restricţii

• 1 <= N <= 10⁹.
• 1 <= K, L, Q <= 1000.
• L < K.
• Pentru unele teste în valoare de 5 puncte K=3.
• Pentru alt teste în valoare de 5 puncte L=2.
• Problema va fi evaluată pe teste în valoare de 90 de puncte.
• Exemplele vor reprezenta teste în valoare de 10 puncte "din oficiu".

Exemplu

Explicaţie

Pentru primul test, tripletele sunt: (1,6,6), (6,1,6), (6,6,1), (2,3,6), (3,2,6), (2,6,3), (6,2,3), (3,6,2), (6,3,2), (6,6,6), (2,6,6), (6,2,6), (6,6,2), (3,6,6), (6,3,6), (6,6,3)
Al doilea test este putin mai complicat.

Cum se trimit solutii?