== include(page="template/taskheader" task_id="nkl") ==

Poveste şi cerinţă...

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

h2. Date de intrare

Fişierul de intrare $test.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $test.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 <= N <= 1000000000$
* $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$
* $Se vor acorda 10 puncte din oficiu$

h2. Exemplu

table(example). |_. test.in |_. test.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. salturi.in |_. salturi.out |
| 6
1
3 2
| 16
|

h3. Explicaţie

...

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

== include(page="template/taskfooter" task_id="nkl") ==