Given a string which only contains '(' and ')' , you are asked to compute the value of the given string based on the following rules.
Supposed that A and B are both string which only contain '(' and ')'.
Rule 1: () = 1
Rule 2: (A) = 2 × A . For example, (()) = 2 × () = 2 × 1 = 2
Rule 3: AB = A + B . For example, ()() = 1 + 1 = 2
Computation process example:
Input string = (()(())) = 2 × ()(()) = 2 × [1 + (())] = 2 × [1 + 2 × ()] = 2 × [1 + 2 × 1] = 6
Notice: We guarantee that the given string is legal to compute. Therefore, testcases will not contain the following illegal cases.
illegal cases examples: ((), ))((
First line contains an integer N which denotes the length of the given string. (2 ≤ N ≤ 100)
Second line contains N characters which denotes the input parentheses string.
An integer which represent the value of the given string. (We guarantee that the answer can be stored in long long)
(Don't forget to print '\n' at the end of the line)