CF2190B2 Sub-RBS (Hard Version)

本题为该问题的困难版本。不同版本间的差异在于：本版本需要计算 $s$ 的**所有子序列**的得分之和；$s$ 不一定是正则括号序列；同时对 $n$ 的约束条件更宽松。 我们称括号序列 $a$ 比括号序列 $b$ **更优**，当且仅当满足以下任一条件： 1. $b$ 是 $a$ 的前缀，但 $a \ne b$； 2. 设 $i$ 是 $a$ 和 $b$ 第一个出现字符不同的位置（若存在），且满足 $a_i = \texttt{(}$ 且 $b_i = \texttt{)}$。 对于任意括号序列 $t$，其**得分**定义如下： 1. 若 $t$ 不是正则括号序列$^{∗}$，则得分为 $0$； 2. 若存在 $t$ 的一个正则括号子序列$^{†}$ $r$ 满足 $r$ 比 $t$ 更优，则得分为所有此类子序列 $r$ 的长度 $|r|$ 的最大值； 3. 否则，得分为 $0$。 换句话说，$t$ 的得分等于：$t$ 的所有“比 $t$ 更优”的正则括号子序列中，最长子序列的长度。若 $t$ 不是正则括号序列，或不存在比 $t$ 更优的正则子序列，则得分为 $0$。 给定一个长度为 $n$ 的括号序列 $s$，请计算 $s$ 的所有**非空**子序列的得分之和，并对 $998\,244\,353$ 取模。 $^{∗}$ 正则括号序列（Regular Bracket Sequence, RBS）的定义：将序列中原有字符间插入字符 $\texttt{1}$ 和 $\texttt{+}$ 后，能转化为合法算术表达式的括号序列。例如： - 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则的（转化后的表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）； - 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 不是正则的。 $^{†}$ 子序列的定义：若序列 $a$ 可通过删除序列 $b$ 中任意位置的若干个（可能为 0 个或全部）元素得到，则称 $a$ 是 $b$ 的子序列。

输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 30$），后续为各测试用例的描述。 每组测试用例的第一行输入一个整数 $n$（$1 \le n \le 100$），表示字符串 $s$ 的长度。 第二行输入一个长度为 $n$ 的字符串 $s$，仅由字符 $\texttt{(}$ 和 $\texttt{)}$ 组成。 保证所有测试用例的 $n$ 之和不超过 $100$。

对于每组测试用例，输出一个整数：$s$ 的所有非空子序列的得分之和，对 $998\,244\,353$ 取模后的结果。

第一个样例中，唯一的非空子序列是 $g = \texttt{(}$。它不是正则括号序列，因此得分为 $0$，总和也为 $0$。 第二个样例中，考虑子序列 $g = s = \texttt{()()()}$：它是正则括号序列。我们可以选择 $r = \texttt{(())}$（$g$ 的一个子序列），$r$ 和 $g$ 第一个出现差异的位置是 $i=2$，且 $r_2 = \texttt{(}$、$g_2 = \texttt{)}$，因此 $r$ 比 $g$ 更优。由此，$g$ 的得分为 $|r| = 4$。$s$ 的其他所有非空子序列的得分均为 $0$，因此总和为 $4$。