Brackets
Young programmer Agnes recently learned about arithmetic expressions in her computer science class. She became curious about what would happen if everything except the brackets were removed from an arithmetic expression. After some research, she discovered that mathematicians refer to sequences of brackets that could appear in an arithmetic expression as valid bracket sequences.
For example, the sequence ()(()) is a valid bracket sequence because it could appear in an expression like (2+2):(3–(5–2)+4), whereas the sequences (() and ())( are not. There are exactly five valid bracket sequences consisting of six brackets (three opening and three closing): ((())), (()()), (())(), ()(()), and ()()().
Agnes became interested in the simplest transformations of valid bracket sequences. She decided to focus on adding brackets to the sequence. She quickly realized that adding one bracket makes the sequence invalid, but adding two brackets can sometimes preserve its validity. For example, by adding two brackets in different places to the sequence ()(), one can obtain the sequences (()()), (())(), ()(()), and ()()(). It is clear that to maintain validity, one of the new brackets must be opening, and the other must be closing.
Agnes wants to count the number of different ways to add two brackets to a given valid bracket sequence so that it remains valid. However, this number can be very large in some cases. Agnes distinguishes the ways of obtaining a sequence by the positions of the added brackets in the resulting sequence. For example, even when adding brackets to the simplest sequence (), one can obtain another valid bracket sequence in seven ways: ()(), (()), (()), (()), (()), ()(), ()(). Here, the added brackets are highlighted in bold.
Thus, if in the resulting sequence the added opening bracket is at position i, and the added closing bracket is at position j, then two ways corresponding to the pairs (i_1, j_1) and (i_2, j_2) are considered different if i_1≠i_2 or j_1≠j_2.
You need to write a program that, given a valid bracket sequence, determines the number of different ways to add two brackets as described above.
Input
The input file consists of a single non-empty line containing exactly 2n characters: n opening and n closing round brackets. It is guaranteed that this line is a valid bracket sequence.
The value of n (the number of brackets of each type) does not exceed 50000.
Output
Output the number of different ways to add two brackets to the given sequence so that it becomes another valid bracket sequence.