Minimal Parentheses Insertion

Given a parentheses sequence S consisting of characters '(' and ')', your task is to insert the minimum number of parentheses into S so that the resulting sequence becomes valid (i.e. a well‐formed parentheses string). In the process of inserting the minimum number of parentheses, different insertion choices may lead to different valid sequences. Two valid sequences are considered essentially different if there exists at least one position at which one sequence has a '(' while the other has a ')'.

Let the given sequence be denoted by S and its length be n. The minimal number of insertions required can be determined as follows:

Initialize balance = 0 and addLeft = 0. For each character c in S:

• If c = '(', then balance++.
• If c = ')' and balance > 0, then balance--; otherwise, addLeft++.

After processing all characters, define addRight = balance. The minimal number of insertions is then $$ L = addLeft + addRight \,. $$

You must count the number of essentially different valid sequences that can be obtained by inserting exactly L parentheses into S (while keeping the order of the characters in S unchanged).

Example: For S = "((()", we have addLeft = 0 and addRight = 2 so that L = 2. The possible essentially different valid sequences are:

• ()()()
• ()(())
• (())()
• (()())
• ((()))

Thus, the answer is 5.

inputFormat

The input consists of a single line containing a string S consisting only of characters '(' and ')'.

outputFormat

Output a single integer representing the number of essentially different valid sequences that can be obtained by inserting the minimum number of parentheses.

sample

((()

5