All Numbers

Fie $N$ un număr natural.

Cerință

Să se determine suma tuturor numerelor naturale cu următoarele proprietăți:

• descompunerea acestora în factori primi conține aceiași factori primi ca și $N$;
• suma exponenților descompunerii în factori primi a acestora este aceeași ca a lui $N$;
• au un număr maxim de divizori.

Date de intrare

Pe prima linie se va găsi numărul natural $N$.

Date de ieșire

Pe prima linie se va găsi un singur număr natural, reprezentând restul împărțirii sumei determinate la numărul $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N \leq 10^{12}$;
• Pentru $24$ de puncte, $1 \le N < 10^{6}$;
• Pentru $28$ de puncte, $10^6 \leq N < 10^{10}$;
• Pentru $48$ de puncte, $10^{10} \leq N \leq 10^{12}$.

Exemplul 1

stdin

20

stdout

70

Explicație

$20 = 2^2\cdot5^1$, $50 = 2^1\cdot5^2$ și ambele numere au un număr maxim de divizori, egal cu $6$.

Restul împărțirii sumei lor la numărul $1 \ 000 \ 000 \ 007$ este egal cu $70$.

Exemplul 2

stdin

945

stdout

7455

Explicație

• $1575 = 3^2\cdot5^2\cdot7^1$;
• $2205 = 3^2\cdot5^1\cdot7^2$;
• $3675 = 3^1\cdot5^2\cdot7^2$.

Toate cele trei numere au un număr maxim de divizori, egal cu $18$.

Restul împărțirii sumei lor la numărul $1 \ 000 \ 000 \ 007$ este egal cu $7455$.

Exemplul 3

stdin

99999999

stdout

833333155

Explicație

Există cinci numere naturale care respectă proprietățile impuse: $566 \ 666 \ 593$, $366 \ 666 \ 612$, $433 \ 333 \ 295$, $366 \ 666 \ 663$ și $99 \ 999 \ 999$.

Suma acestor numere este egală cu $1 \ 833 \ 333 \ 162$, iar restul împărțirii acestui număr la $1 \ 000 \ 000 \ 007$ este egal cu $833 \ 333 \ 155$.