Sum and product

Time limit2sMemory limit1024 MB

Summary

Given n, count the non-increasing sequences of n positive integers whose product equals their sum.

Level: Medium6 of 10
Topics: Math, Number theory, Combinatorics
Solved: No attempts yet

Problem

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, \ldots, a_n$ such that

$a_1 \times a_2 \times \cdots \times a_n = a_1 + a_2 + \cdots + a_n$

and $a_1 \ge a_2 \ge \cdots \ge a_n$ .

You solve this task quickly and convince yourself that such a sequence always exists. Then you start wondering: given a positive integer $n$ , how many sequences have these properties?

Write a program that, for a given positive integer $n$ , counts the sequences of positive integers $a_1, a_2, \ldots, a_n$ that satisfy $a_1 \times a_2 \times \cdots \times a_n = a_1 + a_2 + \cdots + a_n$ and $a_1 \ge a_2 \ge \cdots \ge a_n$ .

Input

The standard input has one line with one positive integer $n$ , the number of terms in each sequence.

Output

Print one line with the number of sequences that satisfy the conditions. Under the constraints below, the answer is finite and smaller than $10^{18}$ .

Constraints

$2 \le n \le 100000000000$

Examples2

Example 1
Input
```
2
```
Expected output
```
1
```
Example 2
Input
```
8
```
Expected output
```
2
```