부분 문자열 표현

트리는 때때로 문자열의 형태로 표현된다. 레이블이 없는 트리를 표현하는 가장 널리 쓰이는 방법 중 하나는 다음과 같다.

• 잎은 "()"로 표현한다.
• 잎이 아닌 노드, 즉 내부 노드는 ( S1 S2 ... Sn )으로 표현한다. 여기서 Si는 i번째 자식 노드를 나타내는 문자열이다.

예를 들어 아래 그림의 트리는 문자열 "((()())())"로 표현된다.

Norward라는 별난 소년이 이런 문자열을 가지고 논다. 그는 문자열에서 연속한 일부분을 하나 제거한 뒤에도 그 문자열이 트리의 표현으로 여전히 올바른 경우가 있다는 것을 알아냈다. 예를 들어 문자열 "((()())())"에서 밑줄 친 부분을 제거하면 "((()))"가 되고, 이는 아래 그림의 트리를 나타낸다.

하지만 그는 이런 제거 방법이 몇 가지인지 알 방법이 없다. 당신의 과제는 그의 호기심을 채워 줄 프로그램을 작성하는 것이다.

입력은 레이블이 없는 어떤 트리를 나타내는 문자열 하나로 이루어진다. 문자열의 길이는 최대 100,000자이다.

주어진 문자열에서 일부분을 제거했을 때 다른 올바른 트리를 나타내는 문자열이 되는 그러한 부분의 개수를 출력한다.