Number in the bracket sequence#5295

Number in the bracket sequence

2 seconds
64 megabytes
Easy

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 .

Input

The first line contains an integer (1 \leq n \leq 30). The second line contains a correct bracket sequence consisting of brackets.

Output

Output the lexicographical number of the given correct bracket sequence.

Examples

Example 1

Loading
Loading