Fie D, K și P trei numere naturale.

Cerința

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

Restricții și precizări

• 2 ≤ D ≤ 1014
• 1 ≤ K ≤ 100
• 2 ≤ P ≤ 1.000.000

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 două numere prime mai mici sau egale decât 5: 2132, 2152, 2231, 2251, 3152, 3251.

Exemplul 2:

divizori.in

18 3 10

divizori.out

12

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 mai mici sau egale cu 17 deoarece sunt doar 7 numere prime mai mici sau egale decât 17.