Brackets

Young programmer Agnessa recently learned about arithmetic expressions in her computer science class. She wondered what happens if everything except the brackets is removed from an arithmetic expression. After entering a query into her favorite search engine, she found out that mathematicians call sequences of brackets that could appear in some arithmetic expression regular bracket sequences.

For example, the sequence ()(()) is a regular bracket sequence, because it can appear, for instance, in the expression (2+2):(3–(5–2)+4), while the sequences (() and ())( are not regular. It is easy to see that there are five regular bracket sequences consisting of exactly six brackets (three of each type, opening and closing): ((())), (()()), (())(), ()(()), and ()()().

Agnessa became interested in the simplest transformations of regular bracket sequences. To start, she decided to restrict herself to adding brackets to a sequence. She quickly found out that after adding one bracket the sequence stops being regular, but adding two brackets sometimes preserves regularity. For example, by adding two brackets at various places in the sequence ()() one can obtain the sequences (()()), (())(), ()(()), and ()()(). It is easy to see that in any way of adding two brackets while preserving regularity, one of the new brackets must be opening and the other closing.

Agnessa wants to count the number of distinct ways to add two brackets to a given regular bracket sequence so that a regular bracket sequence is obtained again. Unfortunately, it turned out that this number can be very large in some cases. Agnessa distinguishes ways of obtaining a sequence by the positions of the added brackets in the resulting sequence. For example, even by adding brackets to the simplest sequence () one can obtain another regular bracket sequence in seven ways: ()(), (()), (()), (()), (()), ()(), ()(). Here the added brackets are shown 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 (i1, j1) and (i2, j2) are considered distinct if i1≠i2 or j1≠j2.

Write a program that, given a regular bracket sequence, determines the number of distinct ways described above to add two brackets.

The input file consists of one non-empty string containing exactly 2n characters: n opening and n closing parentheses. The string is guaranteed to be a regular bracket sequence.

Output the number of distinct ways to add two brackets to the given sequence so that another regular bracket sequence is obtained.

The value n (the number of brackets of each type) does not exceed 50 000.