Номер за дужковою послідовністю

Правильною дужковою послідовністю з 2n дужок називається така послідовність, яка може зустрічатись у деякому арифметичному виразі. Наприклад, ()()() та (())() є правильними дужковими послвдовностями, а (((()) та (()))( - ні.

Усі дужкові послідовності можна упорядкувати у лексикографічному порядку, вважаючи, що ( менше, ніж ). Скажімо, при n=3 список упорядкованих правильних дужкових послідовностей буде виглядати так: ((())),(()()), (())(), ()(()), ()()().

У цій задачі потрібно знайти лексикографічний номер за правильною дужковою послідовністю (нумерація ведеться з нуля).

Вхідні дані

У першому рядку задано число n (1 ≤ n ≤ 30). У другому рядку задано правильну дужкову послідовність з 2n дужок.

Вихідні дані

Виведіть номер правильної дужкової послідовності.

Приклади