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.

千优有一个长度为 $n$ 的括号序列$^\dagger$ $s$。设 $k$ 为千优需从 $s$ 中删除的最少字符数，使得 $s$ 变为一个平衡括号序列$^\ddagger$。

现在，小紫希望你计算：有多少种方式恰好删除 $k$ 个字符，使得 $s$ 变为平衡括号序列？答案对 $998\,244\,353$ 取模。

注意：仅当被删除的下标集合不同时，两种删除方式才被视为不同。

$^\dagger$ 括号序列是指仅由字符 "(" 和 ")" 组成的字符串。

$^\ddagger$ 若一个括号序列可通过添加字符 "+" 和 "1" 转化为合法的数学表达式，则称其为平衡括号序列。例如，序列 (())(), (), (()(())) 以及空字符串是平衡的，而 )(、(() 和 (()))( 则不是。

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 ")".

输入的第一行包含一个字符串 $s$（$1 \leq |s| \leq 5 \cdot {10}^5$）——括号序列。

保证 $s$ 仅包含字符 "(" 和 ")"。

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

输出一个整数——即从字符串 $s$ 中删除 $k$ 个字符，使得 $s$ 变为平衡字符串的方案数，对 $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.

在第一个测试用例中，可以证明千悠需要删除的最少字符数量为 $2$。共有 $4$ 种删除 $2$ 个字符的方式，使得 $s$ 变为平衡括号序列，如下所示（被删除的字符以红色标出）：

• $\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{)}$。

在第二个测试用例中，使 $s$ 平衡的唯一方式是删除唯一的那个字符，从而得到空括号序列；而空括号序列被视为平衡的。