시간 제한메모리 제한제출정답맞힌 사람정답 비율
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).

## 채점 및 기타 정보

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