A correct bracket sequence of length is a sequence that can appear in some arithmetic expression. For example, ()()() and (())() are correct bracket sequences, while (((()) and (()))( are not.
All bracket sequences can be arranged in lexicographical order, where ( is considered less than ). For example, when n=3, the ordered list of correct bracket sequences is: ((())), (()()), (())(), ()(()), ()()().
Your task is to determine the lexicographical number (starting from zero) of a given correct bracket sequence of length .
The first line contains an integer (1 \leq n \leq 30). The second line contains a correct bracket sequence consisting of brackets.
Output the lexicographical number of the given correct bracket sequence.
Example 1