24258번 - Sum and product 서브태스크다국어

Your math teacher has given the following task for homework: given a positive integer n, find a sequence of positive integers a₁, a₂, a₃,…….., a_n, such that

a₁ × a₂ × a₃ × … × a_n = a₁ + a₂ + a₃ + … + a_n and a₁ ≥ a₂ ≥ a₃ ≥……..≥ 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?"

Write the program, which for a given positive integer n finds the number of sequences of positive integers a₁, a₂, a₃,…….., a_n, such that

a₁ × a₂ × a₃ × … × a_n = a₁ + a₂ + a₃ + … + a_n and a₁ ≥ a₂ ≥ a₃ ≥……..≥ a_n

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 10¹⁸.

• 2 ≤ n ≤ 100 000 000 000