P16958 [SCCPC 2026] 括号序列

对于字符串 $S$，$T$，定义 $S$ 的字典序小于 $T$ 当且仅当以下三者之一成立： - $S$ 为空串（长度为 $0$），$T$ 为非空串； - $S,T$ 为非空串，且 $S[0]$ 字典序小于 $T[0]$，这里 $S[0],T[0]$ 表示 $S,T$ 的首个字符； - $S,T$ 为非空串，且 $S[0]=T[0]$，$S[1,\cdots]$ 字典序小于 $T[1,\cdots]$，这里 $S[1,\cdots],T[1,\cdots]$ 表示 $S,T$ 删除首个字符得到的字符串。 对于由 $\texttt{\{`(',`)'\}}$ 组成的括号串 $S$，称其为可匹配的，当且仅当以下三者之一成立： - $S$ 是空串（长度为 $0$）； - $S = (A)$，其中 $A$ 是可匹配的括号串； - $S = AB$，其中 $A$，$B$ 都是可匹配的非空括号串。 下面给出一个可匹配的括号串 $T$，求有多少个括号串 $S$ 满足以下四个条件： - $S$ 不是空串（长度大于 $0$）； - $S$ 是可匹配的； - $S=T$，或 $S$ 的字典序小于 $T$； - $S$ 的长度小于等于 $T$ 的长度。 注意，符号 $\texttt{`('}$ 的字典序比 $\texttt{`)'}$ 小。 本题采用多组测试。答案可能很大，请输出结果对 $998244353$ 取模后的余数。

每个测试点第一行包含一个正整数 $t$（$1 \le t \le 5\times 10^5$），表示数据组数。 接下来 $t$ 组数据，每组数据第一行为一个偶数 $n$（$2\le n\le 10^6$），表示字符串 $T$ 的长度。 第二行为一个长度为 $n$ 的括号串，其字符集为 $\texttt{\{`(',`)'\}}$。这里保证 $T$ 是可匹配的。 保证单个测试点内所有括号串的长度总和不超过 $10^6$。

输出 $t$ 行，第 $i$ 行表示第 $i$ 组数据的答案对 $998244353$ 取模后的余数。

对于第四组数据，有以下六个符合要求的 $S$： - $\texttt{()}$ - $\texttt{(())}$ - $\texttt{()(())}$ - $\texttt{(())()}$ - $\texttt{((()))}$ - $\texttt{(()())}$