Chiyuu 有一个括号序列$$$^\dagger$$$ $$$s$$$,长度为$$$n$$$。令 $$$k$$$ 为 Chiyuu 必须从 $$$s$$$ 中删除以使 $$$s$$$ 平衡$$$^\ddagger$$$ 的最小字符数。
现在,Koxia 希望您计算从 $$$s$$$ 中删除 $$$k$$$ 字符的方法数量,以便 $$$s$$$ 变得平衡,以 $$$998\,244\,353$$$ 为模。
请注意,当且仅当删除的索引集不同时,两种删除字符的方法才被视为不同。
$$$^\dagger$$$ 括号序列是仅包含字符“(”和“)”的字符串。
$$$^\ddagger$$$ 如果可以通过添加字符 + 和 1 将括号序列变成有效的数学表达式,则该括号序列称为平衡的。例如,序列 (())()、()、(()(())) 和空字符串是平衡的,而 )(、(() 和 (()))( 不是平衡的。
输入
输入的第一行包含一个字符串 $$$s$$$ ($$$1 \leq |s| \leq 5 \cdot {10}^5$$$) — 括号序列。
保证$$$s$$$仅包含字符“(”和“)”。
输出
输出一个整数 — 从 $$$s$$$ 中删除 $$$k$$$ 字符以使 $$$s$$$ 变得平衡的方法数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
())(()
输出 #1
4
输入 #2
(
输出 #2
1
注意
在第一个测试用例中,可以证明Chiyuu 必须删除的最少字符数为$$$2$$$。有 $$$4$$$ 方法可以删除 $$$2$$$ 字符以使 $$$s$$$ 平衡,如下所示。删除的字符标记为红色。
- $$$\texttt{(} \color{红色}{\texttt{)}} \texttt{)} \color{红色}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{红色}{\texttt{)}} \color{红色}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \color{红色}{\texttt{)}} \texttt{)} \texttt{(} \color{红色}{\texttt{(}} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{红色}{\texttt{)}} \texttt{(} \color{红色}{\texttt{(}} \texttt{)}$$$。
在第二个测试用例中,使 $$$s$$$ 平衡的唯一方法是删除唯一的字符以获得空括号序列,这被认为是平衡的。