Bracket Coloring_

$\hspace{15pt}$ 小苯有一个长度为 $n$ 、仅由字符 $\texttt{‘(’}$ 和 $\texttt{‘)’}$ 组成的括号序列 $s$ ，且保证这是一个合法括号序列 $^\texttt{[1]}$ 。

$\hspace{15pt}$ 现在他想给每个括号染上红色或蓝色，但需要满足以下条件：
$\hspace{23pt}\bullet\,$ 每一对相互匹配的括号 $^\texttt{[2]}$ 必须染上相同的颜色（即一个 $\texttt{‘(’}$ 和它对应的 $\texttt{‘)’}$ 颜色必须相同）
$\hspace{23pt}\bullet\,$ 若序列中两个相邻位置的括号字符相同（同为 $\texttt{`('}$ 或同为 $\texttt{`)'}$ ），则它们的颜色不能相同。

$\hspace{15pt}$ 请计算有多少种不同的染色方案。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 合法的括号序列 $^\texttt{[1]}$ ：如果在括号序列中插入字符 $\texttt{+}$ 和 $\tt 1$ 就可以得到正确的算术表达式，那么这个括号序列就称为合法的括号序列。例如， $\texttt{$ 、 $\texttt{$ 和 $\texttt{$ 是合法的括号序列，因为填入内容后可以表示为 $\texttt{$ 、 $\texttt{$ 和 $\texttt{$ 。更严格地，一个括号序列被称为合法的括号序列，当且仅当：
${\hspace{20pt}}_\texttt{1.}\,$ 空串是合法的括号序列；
${\hspace{20pt}}_\texttt{2.}\,$ 如果 $A$ 是合法的括号序列，那么 $\texttt{$ 也是合法的括号序列；
${\hspace{20pt}}_\texttt{3.}\,$ 如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是合法的括号序列。

$\hspace{15pt}$ 相互匹配的括号 $^\texttt{[2]}$ ：在合法括号序列中，若左括号 $s_i$ 与右括号 $s_j$ 满足 $i < j$ ，且 $s_{i+1} s_{i+2} \cdots s_{j-1}$ 也是一个合法括号序列，则称这两个位置的括号是相互匹配的。

$\hspace{15pt}$ 每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 10^4\right)$ 代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$ 第一行一个整数 $n\left(2 \leqq n \leqq 2 \times 10^5\right)$ ，保证 $n$ 为偶数。
$\hspace{15pt}$ 第二行一个长度为 $n$ 、仅由字符 $\texttt{‘(’}$ 和 $\texttt{‘)’}$ 组成的括号序列 $s$ ，且保证这是一个合法括号序列。

$\hspace{15pt}$ 除此之外，保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$ 。

Bracket Coloring

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题