常规括号序列是由 ' 组成的序列(' 和 ')',通过将 $$$1$$$ 和 $$$+$$$ 插入序列中任意次数,可以将其转换为有效的数学表达式。例如,序列“()(()())" 是常规括号序列,而 "())(()“或”(()" 不是常规的括号序列。
给你一个常规的括号序列$$$S$$$。
让我们考虑转移 子序列$$$^{\text{*}}$$$ 在右边。形式上,当子序列 $$$S_{i_1} S_{i_2} \ldots S_{i_k}$$$ 向右移动时,所选索引上的字符 同时 重新分配如下:
- $$$S_{i_1} \leftarrow S_{i_k}$$$;
- $$$S_{i_2} \leftarrow S_{i_1}$$$;
- $$$S_{i_3} \leftarrow S_{i_2}$$$;
- $$$\ldots$$$
- $$$S_{i_k} \leftarrow S_{i_{k-1}}$$$。
换句话说,第 $$$j$$$ 个所选索引的元素被重新分配给第 $$$((j-2) \bmod k + 1)$$$ 个所选字符。
例如,当 $$$S$$$ 为“()(()())",将子序列 $$$S_2 S_4$$$ 更改为 "((())())"。另一方面,移位 $$$S_2 S_3 S_5$$$ 将 $$$S$$$ 更改为 "())((())".
请数数有多少 非空子序列 使 $$$S$$$ 向右移动时保持规则。由于答案可能很大,因此只要求您输出对 $$$998\,244\,353$$$ 取模的答案。
$$$^{\text{*}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。如果两个子序列的集合被认为是不同的 职位 删除的元素的 不同。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 300\,000$$$, $$$n$$$ 是偶数).
每个测试用例的第二行包含一个 常规 括号序列 $$$S$$$ 长度为 $$$n$$$ 作为不带空格的字符串给出。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,000$$$。
输出
对于每个测试用例,在单独的行上输出对 $$$998\,244\,353$$$ 取模的答案。
示例
输入复制
42()4()()6(()())10()((())())
输出复制
2828312
注意
对于第二个测试用例,使 $$$S$$$ 向右移动时保持规则的 $$$8$$$ 非空子序列如下:
- $$$S_1$$$:将 $$$S$$$ 更改为 "()()";
- $$$S_2$$$:将 $$$S$$$ 更改为 "()()";
- $$$S_3$$$:将 $$$S$$$ 更改为 "()()";
- $$$S_4$$$:将 $$$S$$$ 更改为 "()()";
- $$$S_1 S_3$$$:将 $$$S$$$ 更改为 "()()";
- $$$S_2 S_3$$$:将 $$$S$$$ 更改为 "(())";
- $$$S_2 S_4$$$:将 $$$S$$$ 更改为 "()()";
- $$$S_1 S_2 S_3$$$:将 $$$S$$$ 更改为 "(())".