Pracsiu Dan (dnprx) Profesorul tău de mate ți-a dat următoarea problemă ca temă: pentru un număr natural nenul n, găsește o secvență de numere naturale nenule a1, a2, a3, …, an astfel încât:
a1 * a2 * a3 *...* an = a1 + a2 + a3 +...+ an și a1 ≥ a2 ≥ a3 ≥...≥ an
Tu reușești să rezolvi repede această problemă și îți dai seama că o astfel de secvență există întotdeauna, dar apoi începi să te gândești la următoarea întrebare: “Dat fiind un număr natural nenul n, care este numărul de secvențe cu proprietățile de mai sus?”
Cerința
Scrie un program care pentru un număr natural nenul n, găsește numărul de secvențe de numere naturale nenule a1, a2, a3,..., an, astfel încât a1 * a2 * a3 *...* an = a1 + a2 + a3 +...+ an și a1 ≥ a2 ≥ a3 ≥...≥ an.
Date de intrare
De la intrărea standard se citește un număr natural nenul n – numărul de numere dintr-o secvență.
Date de ieșire
La ieșirea standard programul trebuie să scrie numărul găsit de secvențe. Se poate demonstra că pentru restricțiile de mai jos răspunsul este un număr finit mai mic decât 1018.
Restricții și precizări
2 ≤ n ≤ 100.000.000.000
Subtask-uri
- Subtask 1 (10 puncte) :
n ≤ 10 - Subtask 2 (10 puncte) :
n ≤ 1.000.000 - Subtask 3 (10 puncte) :
n ≤ 100.000.000 - Subtask 4 (10 puncte) :
n ≤ 1.000.000.000 - Subtask 5 (20 puncte) :
n ≤ 10.000.000.000 - Subtask 6 (40 puncte) :
n ≤ 100.000.000.000
Exemplul 1:
Intrare
2
Ieșire
1
Explicație
Există o singură secvență cu proprietățile specificate și aceasta este (2,2).
Exemplul 2:
Intrare
8
Ieșire
2
Explicație
Cele două secvențe sunt (8, 2, 1, 1, 1, 1, 1, 1) și (3, 2, 2, 1, 1, 1, 1, 1).