Maximum Matching in the Parentheses Generation Tree

Consider a special binary tree defined as follows. The root contains an empty string. For any node with string S, its left child contains S concatenated with a left parenthesis (, and its right child contains S concatenated with a right parenthesis ). However, only the nodes that can eventually lead to a well‐formed parentheses sequence with n pairs are generated; in other words, the tree is generated by the standard recursive procedure for producing all valid parentheses sequences of n pairs. Consequently, each leaf node's string corresponds uniquely to one of the valid parentheses sequences consisting of n pairs.

Your task is to compute the number of edges in a maximum matching of this tree. A matching in a graph is a set of edges without common vertices, and a maximum matching is a matching with the maximum possible number of edges.

Note: If we denote the answer for a given n by M(n), then it turns out that M(n) follows the pattern M(1)=1, M(2)=3, M(3)=9, M(4)=27, etc. In fact, one may prove that
\[ M(n)=3^{n-1} \quad (n\ge1), \]
but you are required to design an algorithm that computes the answer using dynamic programming over the state space of the recursion rather than using the closed‐form formula.

inputFormat

The input is a single integer n (1 ≤ n ≤ 15), which represents the number of pairs of parentheses.

outputFormat

Output a single integer – the number of edges in a maximum matching of the described tree.

sample

1

1