올바른 괄호 문자열을 다음과 같이 정의한다.

• () 와 [] 는 올바른 괄호 문자열이다.
• 만약 A가 올바른 괄호 문자열일 경우, (A) 와 [A] 모두 올바른 괄호 문자열이다.
• 만약 A와 B 모두 올바른 괄호 문자열일 경우, AB 또한 올바른 괄호 문자열이다.

예를 들어, (( 와 ((((())) 둘 다 망가진 괄호 문자열이다.

첫 번째 문자열은 []에서 바뀐 문자열이고, 두 번째 문자열은 []((())), ([](())), (([]())) 또는 ((([])))에서 바뀐 망가진 괄호 문자열이다.

위 예제에서 볼 수 있듯이 망가진 괄호 문자열이 주어졌을 때 그 문자열이 망가지기 전에 가능했던 올바른 괄호 문자열의 가짓수는 여러 가지이다.

우리가 할 일은 이 문제에서 임의의 망가진 문자열이 주어졌을 때, 이 문자열이 망가지기 전에 가능했던 올바른 괄호 문자열의 가짓수를 계산하는 것이다.

입력

• 첫 줄에 망가진 괄호 문자열의 길이 N 이 주어진다. (1 ≤ N ≤ 30,000)
• 둘째 줄에 길이가 N 인 망가진 괄호 문자열이 주어진다.

출력

입출력 예

입력

4
((()

출력

2

입력

8
((((((((

출력

14

힌트

출처: KOI 전국본선대비 모의고사(전명우) 2012년 7월 10일