CF1770G Koxia and Bracket

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 $ .

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.