Problem Description

Little S has a valid bracket sequence of length $n$.

Now Little K sees it and wants to insert some brackets into it, making it a bracket sequence of length $m$ (not necessarily valid). However, she does not want to completely ruin this sequence, so she requires that for her way of inserting brackets, there exists only one valid bracket sequence of length $n$ that can become Little K’s modified sequence by inserting some brackets. In this way, Little S can easily restore the original bracket sequence (that is, under the condition that after deletions the remaining bracket sequence has length $n$ and is valid, no matter how Little S deletes brackets, she can only obtain her initial bracket sequence).

Compute the number of ways for Little K to insert brackets, modulo $998244353$. Two insertion plans are different if and only if we color the final bracket sequence into two types, red for brackets inserted by Little K and black for the original brackets, and the resulting colored bracket sequences are different.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains two integers $n$ and $m$, representing the length of Little S’s bracket sequence and the length after Little K inserts brackets.

The second line contains a valid bracket sequence, representing Little S’s bracket sequence.

Output Format

For each test case, output one line with one integer, the number of plans modulo $998244353$.

2
4 5
(())
2 3
()

8
6

Hint

Sample Explanation

For the first sample, there are $8$ insertion ways as follows:

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

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

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

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

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

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

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

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

The red brackets are those inserted by Little K.

The following way is not allowed:

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

Because you can obtain the following two bracket sequences by deleting the second bracket or the fourth bracket: $(()),()()$.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1\le n\le m$ and $\sum m\le 10^6$, and $1\le T\le 100$.

Translated by ChatGPT 5