Antibody Genome Aggregation

Dr. Smith observed a remarkable phenomenon in African wild monkeys. Initially, each antibody genome is extremely simple and consists of exactly one pair of fundamental gene elements. When exposed to an external virus in a culture, these genomes start to merge—one merge at a time—with the following rule:

When two genomes having a and b pairs merge, they produce a new genome with a total of \[ a \times b + 1 \] pairs. The term +1 represents an extra, mysterious gene pair produced with every merge.

Given that initially there are n antibody genomes (each with 1 pair), the genomes are merged sequentially (only two merge at any one time) until one huge genome remains. Dr. Smith discovered that the process seems to follow an optimal merging strategy that maximizes the final number of gene pairs – and hence the final energy produced (each pair yields 1 unit of biological energy).

Your task is to compute the maximum final number of gene pairs (energy units) obtainable from n initial genomes if the merging order is chosen optimally.

The optimal merging process can be described recursively. Define M(n) to be the maximum number of pairs obtainable with n genomes. We have:

[ M(1)=1,]

[ M(n)=\max_{1\le i<n}{M(i)\times M(n-i)+1}, \quad n\ge2. ]

Compute and output M(n) for the given input.

inputFormat

The input consists of a single integer n (n ≥ 1), which represents the number of initial antibody genomes.

outputFormat

Output a single integer which is the maximum number of gene pairs (i.e. energy units) that can be produced after merging all the genomes optimally.

sample

1

1