题目描述

小 S 有一个长度为 $n$ 的合法括号序列。

现在小 K 看到了，想在其中插入若干括号，使之成为一个长度为 $m$ 的括号序列（不一定合法）。但是她不想完全破坏这个序列，于是她希望对于她这种添加括号的方式，仅存在一种合法的且长度为 $n$ 的括号序可以通过插入若干括号来得到小 K 改后的序列，这样小 S 就可以轻松还原出原来的括号序列了（也就是说在保证删完后的括号序列长度为 $n$ 且合法的情况下，无论小 S 如何删除括号，都只能得到她初始的括号序列）。

求小 K 插入括号的方案数模 $998244353$。两种插入括号的方案不同当且仅当我们将最终的括号序列按照是小 K 所插入的还是原有的两类分别染成红色和黑色，得到的带颜色的括号序列不同。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来对于每一组数据：

第一行两个整数 $n$ 和 $m$ 表示小 S 的括号序列的长度和小 K 插入括号后的长度。

第二行一个合法的括号序列表示小 S 的括号序列。

输出格式

对于每一组数据输出一行一个整数，表示方案数对 $998244353$ 取模的结果。

2
4 5
(())
2 3
()

8
6

提示

样例解释

对于第一组样例，我们有如下 $8$ 种插入方式：

$\textcolor{red}{)}(())$

$((\textcolor{red}{)}))$

$(()\textcolor{red}{)})$

$(())\textcolor{red}{)}$

$\textcolor{red}{(}(())$

$(\textcolor{red}{(}())$

$((\textcolor{red}{(}))$

$(())\textcolor{red}{(}$

其中红色的括号表示小 K 插入的括号。

如下的方式是不可行的：

$(\textcolor{red}{)}())$

因为你可以通过删除第二个括号或第四个括号来获得如下两种括号序列：$(()),()()$。

数据范围

本题采用捆绑测试

对于所有数据，保证 $1\le n\le m$ 且 $\sum m\le 10^6$，$1\le T\le 100$。