divizori

Fie $D$, $K$ și $P$ trei numere naturale.

Cerință

Să se determine numărul de numere naturale, notat cu $T$, având următoarele proprietăți:

• au exact $D$ divizori;
• descompunerea în factori primi a acestor numere conține exact $K$ numere prime;
• toți factorii primi din descompunerea numerelor sunt mici sau egali cu $P$.

Date de intrare

Fișierul de intrare divizori.in conține pe primul rând numerele $D$, $K$ și $P$ cu semnificația de mai sus, despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire divizori.out va conține pe primul rând restul împărțirii numărului $T$ la $3 \ 000 \ 017$.

Restricții și precizări

• $2 \leq D \leq 10^{14}$
• $1 \leq K \leq 10^2$
• $2 \leq P \leq 10^6$

Exemplul 1

divizori.in

6 2 5

divizori.out

6

Explicație

$D = 6$, $K = 2$, $P = 5$
Sunt $T = 6$ numere cu exact $6$ divizori ce conțin în descompunerea în factori primi exact $2$ numere prime mai mici sau egale decăt $5$: $2^1 3^2$, $2^1 5^2$, $2^2 3^1$, $2^2 5^1$, $3^1 5^2$, $3^2 5^1$.

Exemplul 2

divizori.in

18 3 10

divizori.out

12

Explicație

$D = 18$, $K = 3$, $P = 10$
Sunt $T = 12$ numere cu exact $18$ divizori ce conțin în descompunerea în factori primi $3$ numere prime mai mici sau egale decăt $10$: $2^2 3^2 5^1$, $2^2 3^1 5^2$, $2^1 3^2 5^2$, $2^2 3^2 7^1$, $2^2 3^1 7^2$, $2^1 3^2 7^2$, $2^2 5^2 7^1$, $2^2 5^1 7^2$, $2^1 5^2 7^2$, $3^2 5^2 7^1$, $3^2 5^1 7^2$, $3^1 5^2 7^2$.

Exemplul 3

divizori.in

10 8 17

divizori.out

0

Explicație

$D = 10$, $K = 8$, $P = 17$
Nu există numere cu exact $10$ divizori ce conțin în descompunerea în factori primi exact $8$ numere prime $\leq 17$ deoarece sunt doar $7$ numere prime mai mici sau egale decât $17$.