sum_prod

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

$a_1 \cdot a_2 \cdot a_3 \cdot ... \cdot a_n = a_1 + a_2 + a_3 + ... + a_n$ and $a_1 ≥ a_2 ≥ a_3 ≥ ... ≥ 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 $n$, what is the number of sequences with the above properties?"

Task

Write a program which for a given positive integer $n$ finds the number of sequences of positive integers $a_1, a_2, a_3, ..., a_n$, such that

$a_1 \cdot a_2 \cdot a_3 \cdot ... \cdot a_n = a_1 + a_2 + a_3 + ... + a_n$ and $a_1 ≥ a_2 ≥ a_3 ≥ ... ≥ a_n$

Input

From one line of the standard input, read one positive integer $n$ - 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}$.

Constraints

• $2 ≤ n ≤ 100 \ 000 \ 000 \ 000$

Subtask

Subtask 1 (5 points)

• $n ≤ 10$

Subtask 2 (10 points)

• $n ≤ 1 \ 000 \ 000$

Subtask 3 (10 points)

• $n ≤ 100 \ 000 \ 000$

Subtask 4 (10 points)

• $n ≤ 1 \ 000 \ 000 \ 000$

Subtask 5 (20 points)

• $n ≤ 10 \ 000 \ 000 \ 000$

Subtask 6 (45 points)

• $n ≤ 100 \ 000 \ 000 \ 000$

Examples

stdin

2

stdout

1

Explanation

There is only one sequence with the specified properties and it is $(2, 2)$

stdin

8

stdout

2

Explanation

$(8, 2, 1, 1, 1, 1, 1, 1)$ and $(3, 2, 2, 1, 1, 1, 1, 1)$