CF2201C Rigged Bracket Sequence

一个“正规括号序列”是仅由 “(” 和 “)” 组成的序列，可以通过在该序列中随意插入 $1$ 和 $+$ 变成合法的数学表达式。例如，序列“()(()())”是一个正规括号序列，而“())(()”或“(()”都不是正规括号序列。 现在给你一个正规括号序列 $S$。 我们定义右移一个子序列。具体地，若将子序列 $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$ 会变为 “((())())”；若右移 $S_2 S_3 S_5$，则 $S$ 会变为 “())((())”。 请你统计，有多少个非空子序列，在右移后会使 $S$ 仍然保持为一个正规括号序列。由于答案可能非常大，只需输出答案对 $998\,244\,353$ 取模的结果。 $^{\ast}$ 序列 $a$ 是序列 $b$ 的子序列，若 $a$ 可以通过从 $b$ 中删除任意（可能为 0 个或全部）若干个元素后得到。如果所删除元素的位置不同，则认为是不同的子序列。

每组测试数据包含多组用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。 每组用例第一行为一个正偶整数 $n$（$2 \le n \le 300\,000$）。 第二行为一个长度为 $n$ 的正规括号序列 $S$，作为一个没有空格的字符串。 保证所有测试用例的 $n$ 之和不超过 $300\,000$。

对于每组测试用例，输出一个答案，每个答案占一行，对 $998\,244\,353$ 取模。

对于第二个测试用例，能使 $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$ 变为 "(())"。 由 ChatGPT 5 翻译