Koxia and Bracket

给定一个括号序列 $s$，你需要删除 **尽可能少** 的字符使得操作完的序列是个合法括号序列。 请求出所有最优删除方案的数量。$1\le |s|\le 5\times 10^5$，答案对 998244353 取模。 两种方案不同当且仅当存在一个位置在两种方案中一个被删除而另一个没有。

Chiyuu has a bracket sequence $ ^\dagger $ $ s $ of length $ n $ . Let $ k $ be the minimum number of characters that Chiyuu has to remove from $ s $ to make $ s $ balanced $ ^\ddagger $ . Now, Koxia wants you to count the number of ways to remove $ k $ characters from $ s $ so that $ s $ becomes balanced, modulo $ 998\,244\,353 $ . Note that two ways of removing characters are considered distinct if and only if the set of indices removed is different. $ ^\dagger $ A bracket sequence is a string containing only the characters "(" and ")". $ ^\ddagger $ A bracket sequence is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are balanced, while )(, ((), and (()))( are not.

The first line of input contains a string $ s $ ( $ 1 \leq |s| \leq 5 \cdot {10}^5 $ ) — the bracket sequence. It is guaranteed that $ s $ only contains the characters "(" and ")".

Output a single integer — the number of ways to remove $ k $ characters from $ s $ so that $ s $ becomes balanced, modulo $ 998\,244\,353 $ .

())(()

4

(

1

In the first test case, it can be proved that the minimum number of characters that Chiyuu has to remove is $ 2 $ . There are $ 4 $ ways to remove $ 2 $ characters to make $ s $ balanced as follows. Deleted characters are noted as red. - $ \texttt{(} \color{Red}{\texttt{)}} \texttt{)} \color{Red}{\texttt{(}} \texttt{(} \texttt{)} $ , - $ \texttt{(} \texttt{)} \color{Red}{\texttt{)}} \color{Red}{\texttt{(}} \texttt{(} \texttt{)} $ , - $ \texttt{(} \color{Red}{\texttt{)}} \texttt{)} \texttt{(} \color{Red}{\texttt{(}} \texttt{)} $ , - $ \texttt{(} \texttt{)} \color{Red}{\texttt{)}} \texttt{(} \color{Red}{\texttt{(}} \texttt{)} $ . In the second test case, the only way to make $ s $ balanced is by deleting the only character to get an empty bracket sequence, which is considered balanced.