Comfortable String

leejseo was playing with bracket strings on a Christmas with nothing to do. He happened to realize that a string like "(())" has a left-right symmetric shape but is not a palindrome. Although such strings are not palindromes, leejseo thought they have meaning of their own, and decided to call strings like "(())", ")(", and "(()())" symmetric strings.

That is, a bracket string (a string made only of '(' and ')') is a symmetric string if reversing the order of the characters and then replacing '(' and ')' with ')' and '(' respectively yields the string itself. For example, "())(()" and ")(" are symmetric strings, while "((" is not.

Among symmetric strings, leejseo was more interested in correct strings. A correct string is defined as follows:

• "()" is a correct string.
• If S is a correct string, then '('+S+')' is also a correct string.
• If S and T are correct strings, then S+T is also a correct string.
• Every other string is not a correct string.

If a string is both a correct string and a symmetric string, it makes leejseo comfortable, so we call it a comfortable string. If a substring of a string is a comfortable string, we call it a comfortable substring. The characters of a substring must occupy consecutive positions in the original string. For example, in the string "()()", "((" is not a substring, and the substring made of the 1st and 2nd characters of "()()" and the substring made of the 3rd and 4th characters are both "()" but are treated as distinct.

Given a bracket string, find the number of comfortable substrings.

The first line of input contains a bracket string S whose length is at least 1 and at most 5,000.

Print the number of comfortable substrings of S.