Maximum Product Partition

Given a positive integer \(n\) (with \(10 \le n \le 31000\)), partition \(n\) into a sum of positive integers such that the product of these numbers is maximized. For example, for \(n = 13\), one optimal partition is \(4+3+3+3\) (or equivalently \(2+2+3+3+3\)), yielding a maximum product of 108.

The optimal strategy is based on the following idea: if you break \(n\) into parts of 3 as much as possible, you generally get the maximum product. However, when the remainder after dividing \(n\) by 3 is 1, it is better to convert one group of \(3+1\) into \(2+2\) (i.e. multiply by 4 instead of \(3 \times 1\)). Formally, if we write \(n = 3q + r\) then:

• If \(r = 0\), the maximum product is \(3^q\).
• If \(r = 1\), the maximum product is \(3^{q-1} \times 4\).
• If \(r = 2\), the maximum product is \(3^q \times 2\).

Your task is to compute and output this maximum product. Note that the product can be extremely large, so you might need to use arbitrary precision arithmetic.

inputFormat

The input consists of a single positive integer \(n\) (\(10 \le n \le 31000\)), read from standard input.

outputFormat

Output the maximum product obtainable by partitioning \(n\) into a sum of positive integers.

sample

10

36