\textit{Правильною дужковою послідовністю} з \textbf{2n} дужок називається така послідовність, яка може зустрічатись у деякому арифметичному виразі. Наприклад, \textbf{()()()} та \textbf{(())()} є правильними дужковими послвдовностями, а \textbf{(((())} та \textbf{(()))(} - ні. Усі дужкові послідовності можна упорядкувати у лексикографічному порядку, вважаючи, що \textbf{(} менше, ніж \textbf{)}. Скажімо, при \textbf{n=3} список упорядкованих правильних дужкових послідовностей буде виглядати так: \textbf{((()))},\textbf{(()())}, \textbf{(())()}, \textbf{()(())}, \textbf{()()()}. У цій задачі потрібно знайти лексикографічний номер за правильною дужковою послідовністю (нумерація ведеться з нуля). \InputFile У першому рядку задано число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{30}). У другому рядку задано правильну дужкову послідовність з \textbf{2n} дужок. \OutputFile Виведіть номер правильної дужкової послідовності.