\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 Выведите номер правильной скобочной последовательности.