Latam++

세계에는 아직 프로그래밍 언어가 충분하지 않다. 이를 돕기 위해 ICPC 내부 위원회(Internal Committee for the Perfection of C, ICPC)가 새 프로그래밍 언어 Latam++를 만들 계획을 세웠다.

Latam++에서 변수 이름은 영어 소문자 하나 이상으로만 이루어진다. 올바른 식(valid expression)은 "well-formed" 문자열이며, 변수를 사칙연산 이항 연산자 "+", "-", "*", "/"로 결합하고 필요하면 괄호로 묶어 나타낸다.

형식적으로, 올바른 식은 다음 규칙으로 만들어지는 문자열과 정확히 일치한다.

• 변수 이름은 올바른 식이다.
• 올바른 식을 괄호로 감싸면 또 다른 올바른 식이 된다.
• A와 B가 올바른 식이면, 둘을 연산자 c로 이어 붙인 AcB도 올바른 식이다. 여기서 c는 "+", "-", "*", "/" 중 하나이다.

따라서 다음은 모두 올바른 식이다.

• a+b
• a+b*(c+b)
• atoms+boots*(charly+bob)
• (((a)))*(bbasdsaqwe/a/a/a)

반대로 다음은 올바른 식이 아니다.

• a+
• a+b(c+b)
• atoms+boots*((charly+bob)
• ((()))*(bbasdsaqwe/a/a/a)

이 언어는 아직 완성되지 않았다. 첫 번째 버전이 나오기까지 ICPC에서 수십 년의 논의가 필요할 것이다. 그동안 이 문제는 컴파일러의 기능 하나, 즉 자동 올바른 부분 문자열 식 개수 세기(Automatic Valid Substring Expression Counting, AVSEC)만 다룬다.

AVSEC는 주어진 문자열의 부분 문자열 중 올바른 식인 것의 총 개수를 컴파일러가 알려주는 기능이다. 여러분의 과제는 AVSEC를 구현하는 것이다.

개수를 셀 때, 시작 위치나 끝 위치가 다른 두 부분 문자열은 문자열 내용이 같더라도 서로 다른 것으로 본다(즉, 같은 문자 순서라도 위치가 다르면 따로 센다).

입력은 한 줄로 이루어지며, 문자열 $S$ ($1 \le |S| \le 2 \times 10^5$)가 주어진다. $S$는 영어 소문자, 여는 괄호와 닫는 괄호, 그리고 "+", "-", "*", "/" 네 문자로 이루어진다.

$S$의 부분 문자열 중 올바른 식인 것의 개수를 정수 하나로 한 줄에 출력한다.