CF2190B2.Sub-RBS (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, you need to find the sum of scores over all subsequences of $s$; $s$ is not necessarily a regular bracket sequence, and the constraints on $n$ are lower.

We say that a bracket sequence $a$ is better than a bracket sequence $b$ if one of the following holds:

• $b$ is a prefix of $a$, but $a \ne b$; or
• let $i$ be the first position (if it exists) where $a_i \neq b_i$, then $\color{red}{a_i = \texttt{(}}$ and $\color{red}{b_i = \texttt{)}}$.

For an arbitrary bracket sequence $t$, we define its score in the following way:

• If $t$ is not a regular bracket sequence$^{\text{∗}}$, the score is $0$.
• If there exists a regular bracket subsequence $^{\text{†}}$ $r$ of $t$ such that $r$ is better than $t$, then the score is equal to the maximum value of $|r|$ over all such subsequences $r$.
• Otherwise, the score is $0$.

In other words, the score of $t$ is the length of the longest regular bracket subsequence of $t$ which is better than $t$. If $t$ is not a regular bracket sequence, or if no regular subsequence better than $t$ exists, the score is $0$.

You are given a bracket sequence $s$ of length $n$. Find the sum of the scores of all non-empty subsequences of $s$ modulo $998\,244\,353$.

$^{\text{∗}}$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $\texttt{1}$ and $\texttt{+}$ between the original characters of the sequence. For example:

• bracket sequences $\texttt{()()}$ and $\texttt{(())}$ are regular (the resulting expressions are $\texttt{(1)+(1)}$ and $\texttt{((1+1)+1)}$);
• bracket sequences $\texttt{)(}$, $\texttt{(}$, and $\texttt{)}$ are not.

$^{\text{†}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

这是该问题的困难版本。两个版本的区别在于：在本版本中，你需要计算字符串 $s$ 的所有子序列的得分之和；$s$ 不一定是合法括号序列，且 $n$ 的约束更小。

我们称括号序列 $a$ 优于括号序列 $b$，当且仅当满足以下任一条件：

• $b$ 是 $a$ 的前缀，但 $a \ne b$；或
• 设 $i$ 为第一个满足 $a_i \neq b_i$ 的位置（若存在），则 $\color{red}{a_i = \texttt{(}}$ 且 $\color{red}{b_i = \texttt{)}}$。

对任意括号序列 $t$，其得分定义如下：

• 若 $t$ 不是合法括号序列$^{\text{∗}}$，则得分为 $0$；
• 若存在 $t$ 的一个合法括号子序列$^{\text{†}}$ $r$，使得 $r$ 优于 $t$，则得分为所有此类子序列 $r$ 中 $|r|$ 的最大值；
• 否则，得分为 $0$。

换言之，$t$ 的得分即为所有优于 $t$ 的 $t$ 的合法括号子序列的最长长度。若 $t$ 本身不是合法括号序列，或不存在优于 $t$ 的合法括号子序列，则得分为 $0$。

给定一个长度为 $n$ 的括号序列 $s$，请计算 $s$ 的所有非空子序列的得分之和，并对 $998\,244\,353$ 取模。

$^{\text{∗}}$ 合法括号序列是指：通过在原序列字符之间插入字符 $\texttt{1}$ 和 $\texttt{+}$，可将其转化为一个正确的算术表达式。例如：

• 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是合法的（对应表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）；
• 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 均不合法。

$^{\text{†}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中任意位置删除若干（可能为零个或全部）元素得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 30$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the string $s$.

The second line of each test case contains a sequence $s$ of length $n$ consisting only of characters $\texttt{(}$ and $\texttt{)}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $100$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 30$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的序列 $s$，其中仅由字符 $\texttt{(}$ 和 $\texttt{)}$ 组成。

保证所有测试用例的 $n$ 之和不超过 $100$。

For each test case, print a single integer — the sum of the scores of all subsequences of $s$, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——字符串 $s$ 的所有子序列的得分之和，对 $998\,244\,353$ 取模。

In the first example, the only non-empty subsequence is $g = \texttt{(}$. It is not a regular bracket sequence, so its score is $0$, and the total sum is also $0$.

In the second example, consider $g = s = \texttt{()()()}$. It is a regular bracket sequence. We can choose $r = \texttt{(())}$, which is a subsequence of $g$. The first index where $r$ and $g$ differ is $i = 2$. Since $r_2 = \texttt{(}$ and $g_2 = \texttt{)}$, $r$ is better than $g$. Hence, the score of $g$ is $|r| = 4$. All the other non-empty subsequences of $s$ have scores equal to $0$.

在第一个例子中，唯一的非空子序列是 $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$。