시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.000%

문제

Your math teacher has given the following task for homework: given a positive integer n, find a sequence of positive integers a1, a2, a3,…….., an, such that

a1 × a2 × a3 × … × an = a1 + a2 + a3 + … + an and a1 ≥ a2 ≥ a3 ≥……..≥ an

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?"

Write the program, which for a given positive integer n finds the number of sequences of positive integers a1, a2, a3,…….., an, such that

a1 × a2 × a3 × … × an = a1 + a2 + a3 + … + an and a1 ≥ a2 ≥ a3 ≥……..≥ an

입력

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

출력

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 1018.

제한

  • 2 ≤ n ≤ 100 000 000 000

서브태스크

번호 배점 제한
1 5

n ≤ 10

2 10

n ≤ 1 000 000

3 10

n ≤ 100 000 000

4 10

n ≤ 1 000 000 000

5 20

n ≤ 10 000 000 000

6 45

n ≤ 100 000 000 000

예제 입력 1

2

예제 출력 1

1

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

예제 입력 2

8

예제 출력 2

2

The two sequences are (8, 2, 1, 1, 1, 1, 1, 1) and (3, 2, 2, 1, 1, 1, 1, 1).

채점 및 기타 정보

  • 예제는 채점하지 않는다.