Sum and product#10959
Sign in

Sum and product

2.6 seconds
256 megabytes
Hard

Your math teacher has given the following task for homework: given a positive integer , find a sequence of positive integers a_1, a_2, a_3, \ldots, a_n, such that

a_1 * a_2 * a_3 * \dots * a_n = a_1 + a_2 + a_3 + \dots + a_n \text{ and } a_1 \geq a_2 \geq a_3 \geq \dots \geq a_n

You quickly solve this task and by doing so, you convince yourself that such a sequence always exists but then you start thinking about the question: "Given a positive integer , what is the number of sequences with the above properties?"

Task: Write the program sum_prod, which for a given positive integer finds the number of sequences of positive integers a_1, a_2, a_3, \ldots, a_n, such that

a_1 * a_2 * a_3 * \dots * a_n = a_1 + a_2 + a_3 + \dots + a_n \text{ and } a_1 \geq a_2 \geq a_3 \geq \dots \geq a_n

Input

From one line of the standard input, read one positive integer – the count of the numbers in the sequences.

Output

On one line of the standard output, the program has to write the found number of sequences. We know, it can be proven that given the constraints below, the answer is a finite number smaller than 10^{18}.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

For n = 2: There is only one sequence with the specified properties and it is .

For n = 8: The two sequences are (8, 2, 1, 1, 1, 1, 1, 1) and (3, 2, 2, 1, 1, 1, 1, 1).

Scoring

2 \leq n \leq 100\,000\,000\,000

Subtask

Points

1

5

2

10

\leq 1\,000\,000

3

10

\leq 100\,000\,000

4

10

\leq 1\,000\,000\,000

5

20

\leq 10\,000\,000\,000

6

45

\leq 100\,000\,000\,000

The points for a subtask are given only if all the tests are successfully passed.