Bracket Sequence Transformation

A legal bracket sequence is defined recursively as follows:

• () and [] are legal bracket sequences.
• If \(A\) is a legal bracket sequence then \((A)\) and \([A]\) are also legal bracket sequences.
• If \(A\) and \(B\) are legal bracket sequences then their concatenation \(AB\) is also a legal bracket sequence.

Consider any legal bracket sequence which contains at least one pair of square brackets. Replace every occurrence of [ and ] with ( (i.e. both square brackets become the character (). This process may produce an illegal bracket sequence. For example:

• The sequence (( can be obtained from the legal sequence [].
• The sequence ((((()))) can be obtained from any one of the following four legal bracket sequences: []((())), ([](())), (([]())) and ((([ ]))) (here, spaces are only for clarity).

Given a bracket sequence S (which is illegal as a bracket sequence) that results from such a transformation, your task is to count the number of legal bracket sequences (according to the definition above) that contain at least one pair of square brackets and which would yield exactly S when every [ and ] is replaced by (.

Note: In the transformation, the characters ( and ) remain unchanged, while both [ and ] are turned into (.

Input Format Discussion: The input consists of a single line that contains the transformed sequence.

Output: Output a single integer representing the number of legal original bracket sequences (which must include at least one square pair) that yield the given sequence after transformation.

Hint: Use a recursive dynamic programming approach. Let \(dp(l, r)\) be a pair \((a, b)\) where \(a\) is the number of ways to form a valid sequence from indices \(l\) to \(r\) without using any square bracket pair, and \(b\) is the number of ways to form a valid sequence that uses at least one square bracket pair. When forming a matching pair from position \(l\) and some matching position \(k\), you have two cases:

• Round Pair: Use ( and ) with conditions \(S[l]=='('\) and \(S[k]==')'\). This does not introduce any square bracket.
• Square Pair: Use [ and ] with conditions \(S[l]=='('\) and \(S[k]=='(' \) because \( f(']') = '(' \). This pair always contributes a square bracket.

Combine the results from the inside and the outside (after the pair) to update the status accordingly. The final answer is \(dp(0, n-1)_{square}\), i.e. the number of ways that use at least one square pair.

inputFormat

The input consists of a single line containing a string S composed of characters (' and ')'. It is guaranteed that S is obtained from a legal bracket sequence (which contains at least one pair of square brackets) by replacing every [ and ] with (, and that S itself is an illegal bracket sequence.

Constraints: The length of S is even and reasonably small (so that a DP solution is feasible).

outputFormat

Output a single integer: the number of legal original bracket sequences that contain at least one pair of square brackets and yield S after replacing every square bracket with (.

sample

((

1