The Monster

As Will은 Upside Down에 갇혀 있지만, 크리스마스 조명을 통해 자신의 엄마 Joyce와 여전히 의사소통할 수 있다(그는 생각만으로 조명을 켜고 끌 수 있다). 그는 자신을 Upside Down로 데려간 괴물이 알아채고 다른 곳으로 옮길 것이기 때문에 자신이 어디에 있는지 엄마에게 직접 말할 수 없다.

그래서 그는 자신의 좌표를 엄마에게 알려 주기 위한 퍼즐을 생각해 냈다. 그의 좌표는 다음 문제의 답이다.

괄호('('와 ')')로만 이루어진 문자열을 괄호 문자열이라고 한다. 일부 괄호 문자열을 올바른 괄호 문자열이라고 한다. 더 형식적으로는 다음과 같다.

• 빈 문자열은 올바른 괄호 문자열이다.
• s가 올바른 괄호 문자열이면, (s)도 올바른 괄호 문자열이다.
• s와 t가 올바른 괄호 문자열이면, st(s와 t를 이어 붙인 문자열)도 올바른 괄호 문자열이다.

괄호와 물음표('?')로 이루어진 문자열에서 각 물음표를 '(' 또는 ')' 중 하나로 바꾸어 그 결과가 비어 있지 않은 올바른 괄호 문자열이 되게 하는 방법이 존재할 때, 그리고 그럴 때에만 이 문자열을 아름답다고 한다.

Will은 조명을 통해 모스 부호를 사용하여 괄호와 물음표로 이루어진 문자열 s를 엄마에게 보냈으며, 그의 좌표는 1 ≤ l ≤ r ≤ |s|이고 문자열 slsl + 1... sr가 아름다운 정수 쌍(l, r)의 개수이다. 여기서 si는 s의 i-th번째 문자이다.

Joyce는 괄호 문자열에 관해 아무것도 모르므로, 당신에게 도움을 요청했다.

입력의 첫 번째이자 유일한 줄에 문자 '(', ')', '?'로만 이루어진 문자열 s (2 ≤ |s| ≤ 5000)가 주어진다.

출력의 첫 번째이자 유일한 줄에 Will의 퍼즐에 대한 답을 출력한다.

첫 번째 예제 테스트 케이스에서 s의 아름다운 부분 문자열은 다음과 같다.

1. "(?"는 "()"로 바꿀 수 있다.
2. "?)"는 "()"로 바꿀 수 있다.
3. "((?)"는 "(())"로 바꿀 수 있다.
4. "(?))"는 "(())"로 바꿀 수 있다.

두 번째 예제 테스트 케이스에서 s의 아름다운 부분 문자열은 다음과 같다.

1. "??"는 "()"로 바꿀 수 있다.
2. "()".
3. "??()"는 "()()"로 바꿀 수 있다.
4. "?()?"는 "(())"로 바꿀 수 있다.
5. "??"는 "()"로 바꿀 수 있다.
6. "()??"는 "()()"로 바꿀 수 있다.
7. "??()??"는 "()()()"로 바꿀 수 있다.