Description

For some reason, although Little A always does his own things in class, he finishes every assigned homework in just a dozen minutes. You are curious why he is so skilled, but right now, what Little A is doing in class seems even more interesting to you.

“You never listen carefully in class every week. What are you doing?”

“I feel the teacher’s lectures are pretty shallow, so I just make something for fun. At most it’s related to the course. Like designing some automata and testing what states they can accept.” Little A stared at the draft paper in front of his laptop.

After a while, Little A saw a bunch of parentheses appear on his screen. You guessed he might be designing an automaton to check whether a parenthesis sequence is matched. But just as you were about to talk to Little A, he suddenly pointed at the screen and said, “Does this make sense? I originally typed a parenthesis sequence for testing, but my hand slipped and the cursor got to some weird place. I kept staring for a long time and couldn’t find what was wrong with the program. Turns out I typed it wrong.”

You replied with a bitter smile, “Doesn’t that happen all the time? As long as you know where the problem is.”

Unexpectedly, this made Little A even more annoyed.

“You say it happens all the time? Then I’ll give you this string. Try to see how many ways there are to turn it back into a valid parenthesis sequence.”

To be fair, it’s not that you can’t compute it, but you would rather listen to the lecture. Unfortunately, you didn’t manage to interrupt Little A’s next sentence.

“Deal then. If you can’t figure it out before class ends, treat me to a spicy hot pot.”

Input Format

The input contains only one string $s$, representing the string that Little A actually typed. It is guaranteed that $s$ contains only ( and ), and the counts of the two are equal.

Output Format

Output one integer, representing the number of essentially different restoration plans.

We say a plan can restore a parenthesis sequence $s=s_1 s_2 \cdots s_n$ if and only if there exists a partition $s=uvw$ such that $uwv$ is a valid parenthesis sequence. Here, $u=s_1\cdots s_l$ may be the empty string (in this case $l=0$), but $v=s_{l+1}\cdots s_r$ and $w=s_{r+1}\cdots s_n$ are non-empty strings. We call two restoration plans essentially different if and only if $l$ is different between the two plans or $r$ is different; even if the restored strings are the same, the two restoration plans may still be essentially different.

()()()

6

Hint

Sample Explanation

All possible restoration plans are (where the parts before and after the arrow are $s=u+v+w$ and $uwv$, respectively):

1. $l=0,r=2$, corresponding to $\varepsilon$ (empty string, same below) $+$()$+$()() $\Rightarrow$ ()()()；
2. $l=0,r=4$, corresponding to $\varepsilon+$()()$+$()$\Rightarrow$()()()；
3. $l=1,r=2$, corresponding to ($+$)$+$()()$\Rightarrow$(()())；
4. $l=1,r=4$, corresponding to ($+$)()$+$()$\Rightarrow$(())()；
5. $l=2,r=4$, corresponding to ()$+$()$+$()$\Rightarrow$()()()；
6. $l=3,r=4$, corresponding to ()($+$)$+$()$\Rightarrow$()(())。

Among these partitions, plans $1,2,5$ produce the same string as the input string, but this does not affect the fact that they have different partition methods.

In addition, ()()$+$()$+\varepsilon$ and ()()$+\varepsilon+$() are not valid restoration plans, because in the former partition $w=\varepsilon$, while in the latter partition $v=\varepsilon$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le |s| \le 10,000,000$.

Hint

You do not need to know any course content related to Formal Languages and Automata to solve this problem.

Also, the claim that the course Formal Languages and Automata is “very easy” is only the opinion of the fictional character Little A in this problem, and does not represent the problem setter’s view.

Problem Source

From the 2021 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2021).

Editorials and other resources can be found at https://github.com/yylidiw/thupc_0/tree/master.

Translated by ChatGPT 5