Background

"Formal Languages and Automata" is a core professional course offered by the Department of Computer Science at T University. In this course, you learn about "common language classes and their corresponding computational models, as well as the relationships between these models." This course involves quite a bit of obscure theoretical knowledge; however, for your good friend Xiao A, who has won trophies in international competitions, it seems a bit too simple.

Description

For some reason, although Xiao A is always doing his own thing during class, he finishes every assigned homework in just over ten minutes. You are curious about why Xiao A is so proficient, but right now, what Xiao A is doing in class seems more interesting to you.

"You never pay attention in class every week; what are you doing?"

"I think the teacher's lectures are quite boring, so I'm just playing around with some stuff. At most, it's related to the course—just designing some automata or something to test what states they can accept," Xiao A said, staring at the scratch paper in front of his computer.

After a while, Xiao A saw a bunch of parentheses appear on his screen. You guessed that he might have designed an automaton to determine if a parenthesis sequence is balanced. But just as you were about to strike up a conversation with Xiao A, he suddenly pointed at the screen and said to you: "Tell me, is this reasonable? I originally entered a test parenthesis sequence, but my hand slipped and I moved the cursor to a weird place. I was wondering why I couldn't see what was wrong with the program for so long; it turns out I entered it wrong."

You replied with a wry smile: "Doesn't that happen all the time? At least you know where the problem is now."

Unexpectedly, this sentence made Xiao A even more irritable.

"You say it happens all the time? Then here is this string; try to see how many ways there are to turn it back into a valid parenthesis sequence."

Admittedly, it's not that you don't know how to calculate it, but you would rather listen to the lecture. Unfortunately, you didn't get a chance to interrupt Xiao A's next sentence.

"It's a deal then. If you haven't figured it out before class ends, you're buying me hot pot."

Input

The input consists of a single string $s$, representing the string Xiao A actually entered. It is guaranteed that $s$ contains only ( and ), and the number of each is equal.

Output

Output an integer representing the number of distinct restoration schemes.

We define a scheme that 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$ can be an empty string (in which case $l=0$), but $v=s_{l+1}\cdots s_r$ and $w=s_{r+1}\cdots s_n$ must not be empty strings. We say two restoration schemes are distinct if and only if the $l$ or $r$ in the two schemes are different; even if the strings restored by two schemes are identical, the two schemes may still be distinct.

Examples

Input 1

()()()

Output 1

6

Note 1

All possible restoration schemes are (where the arrows point from $s=u+v+w$ to $uwv$):

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 partition schemes, schemes 1, 2, and 5 restore the same string as the input string, but this does not affect the fact that their partition methods are different.

Additionally, ()() $+$ () $+\varepsilon$ and ()() $+\varepsilon +$ () are not valid restoration schemes because in the former partition $w=\varepsilon$, and in the latter partition $v=\varepsilon$.

Input 2

See 2.in and 2.ans in the additional files.

Output 2

See 2.in and 2.ans in the additional files.

Input 3

See 3.in and 3.ans in the additional files.

Output 3

See 3.in and 3.ans in the additional files.

Subtasks

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

Note

You do not need to master the knowledge of the "Formal Languages and Automata" course to solve this problem.

Additionally, the claim that the "Formal Languages and Automata" course is "very simple" is only the opinion of the fictional character Xiao A and does not represent the opinion of the problem setter.