Maximize Product of Distinct Summands

Given a positive integer \(n\), your task is to partition it into several distinct natural numbers (or leave it as a single number \(n\)) such that the product of these numbers is maximized. For example:

• For \(n=3\): The only partition into distinct numbers is \(1+2\) with product \(1\times2=2\), but using \(3\) alone gives a product of 3, which is optimal.
• For \(n=5\): The partitions are \(1+4\) (product = 4) and \(2+3\) (product = 6), so the answer is 6.
• For \(n=6\): The partitions are \(1+5\) (product = 5) and \(2+4\) (product = 8), so the answer is 8.

Note: A partition may consist of a single term (\(n\) itself) if that provides the maximum product.

inputFormat

The input consists of a single positive integer \(n\). You may assume that \(n\) is small enough (for example, \(1 \le n \le 50\)) for a recursive solution to run in time.

outputFormat

Output a single integer which is the maximum product obtainable by partitioning \(n\) into distinct natural numbers that sum to \(n\).

sample

1

1