A gift-wrapping machine forms ribbon loops encoded as strings of ( and ). A string is balanced if it uses exactly n opening brackets and n closing brackets, and in every prefix the number of opening brackets is at least the number of closing brackets.
Count how many distinct balanced strings use exactly n pairs of brackets.
Input format
A single line: the integer n.
Output format
A single integer: the number of balanced bracket strings with exactly n pairs.
Constraints
- 0 <= n <= 18