괄호

어린 프로그래머 아그네사는 정보 수업에서 산술식에 대해 배웠다. 그녀는 산술식에서 괄호를 제외한 모든 것을 지우면 어떻게 되는지 궁금해졌다. 즐겨 쓰는 검색 엔진에 질문을 넣어 본 결과, 어떤 산술식에 나타날 수 있는 괄호열을 수학자들이 올바른 괄호열이라고 부른다는 것을 알게 되었다.

예를 들어 ()(())는 (2+2):(3–(5–2)+4) 같은 식에 나타날 수 있으므로 올바른 괄호열이다. 반면 (()와 ())(는 올바른 괄호열이 아니다. 괄호가 정확히 여섯 개(여는 괄호 세 개, 닫는 괄호 세 개)인 올바른 괄호열은 다섯 개라는 것을 쉽게 알 수 있다: ((())), (()()), (())(), ()(()), ()()().

아그네사는 올바른 괄호열에 가할 수 있는 가장 단순한 변환에 관심을 가졌다. 우선 그녀는 괄호를 추가하는 것만 생각하기로 했다. 괄호를 하나 추가하면 그 열은 더 이상 올바르지 않게 되지만, 괄호를 두 개 추가하면 올바름이 유지되는 경우도 있다는 것을 곧 알아냈다. 예를 들어 ()()의 여러 위치에 괄호 두 개를 추가하면 (()()), (())(), ()(()), ()()()를 얻을 수 있다. 올바름을 유지하면서 괄호 두 개를 추가하는 어떤 방법에서든 새로 추가된 괄호 하나는 여는 괄호이고 다른 하나는 닫는 괄호여야 한다는 것도 쉽게 알 수 있다.

아그네사는 주어진 올바른 괄호열에 괄호 두 개를 추가해 다시 올바른 괄호열을 만드는 서로 다른 방법의 수를 세려고 한다. 안타깝게도 이 수는 어떤 경우에는 매우 커질 수 있다. 아그네사는 결과 열에서 추가된 괄호의 위치로 방법을 구분한다. 예를 들어 가장 단순한 열 ()에 괄호를 추가해도 다른 올바른 괄호열을 일곱 가지 방법으로 얻을 수 있다: ()(), (()), (()), (()), (()), ()(), ()(). 여기서 추가된 괄호는 굵게 표시했다.

따라서 결과 열에서 추가된 여는 괄호가 i번 위치에 있고 추가된 닫는 괄호가 j번 위치에 있다면, 두 방법 (i1, j1)과 (i2, j2)는 i1≠i2 또는 j1≠j2일 때 서로 다른 것으로 본다.

주어진 올바른 괄호열에 대해 위에서 설명한 대로 괄호 두 개를 추가하는 서로 다른 방법의 수를 구하는 프로그램을 작성해야 한다.

입력 파일은 정확히 2n개의 문자로 이루어진 비어 있지 않은 한 줄이다. 문자는 여는 괄호 n개와 닫는 괄호 n개다. 이 문자열이 올바른 괄호열임이 보장된다.

주어진 열에 괄호 두 개를 추가해 다른 올바른 괄호열을 만드는 서로 다른 방법의 수를 출력한다.

n(각 종류의 괄호 개수)은 50 000을 넘지 않는다.