Count Balanced Parentheses Strings

Given an integer N, determine the number of unique balanced parentheses strings that can be formed using exactly N characters. A string is considered balanced if every opening parenthesis '(' is properly matched with a closing parenthesis ')'. If N is odd, output 0 since no balanced configuration is possible.

The answer is given in terms of the Catalan numbers. More formally, if N is even, let m = N/2. The number of balanced parentheses strings is equal to the m-th Catalan number, which can be computed using the formula:

$$ C_m = \frac{1}{m+1} \binom{2m}{m} $$

This problem can be solved using dynamic programming to compute the Catalan numbers.

inputFormat

The input consists of a single integer N (read from standard input) which represents the length of the parentheses string.

outputFormat

Output a single integer (to standard output) representing the number of unique balanced parentheses strings of length N. If N is odd, output 0.

6

5