题目描述

Y 同学正在检查一些尚未写完的括号序列。一个合法括号序列长度为 $2N$ ，由 $N$ 个左括号和 $N$ 个右括号组成，并且从左到右读任意前缀时，左括号数量都不少于右括号数量。

现在给定一个已经写好的前缀 $S$ ，Y 同学想知道有多少种方式可以继续添加括号，使得最终得到一个长度为 $2N$ 的合法括号序列。如果前缀本身已经违反合法括号序列的前缀条件，或者左右括号数量不可能补足，则答案为 $0$ 。

请你回答多个这样的询问，输出每个答案对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $Q$ 。

接下来 $Q$ 行，每行先给出一个整数 $N$ ，再给出一个仅由 ( 与 ) 组成的字符串 $S$ 。

对每个询问输出一行一个整数，表示补全方案数对 $998244353$ 取模后的结果。

3
3 ((
3 ()
4 (()

3
2
5

对于 $100\%$ 的数据，保证 $1\le Q\le 2\times 10^5$ ， $1\le N\le 10^6$ ，所有 $S$ 的长度之和不超过 $2\times 10^5$ 。

测试点编号	分值	$Q \le$	$N \le$	$\sum \vert S \vert \le$	特殊性质
$1\sim 4$	$16$	$20$	$12$	$240$	无
$5\sim 8$	$16$	$2\times 10^5$	$10^6$	$2\times 10^5$	特殊性质 A
$9\sim 12$	$18$	$2\times 10^5$	$10^6$	$2\times 10^5$	特殊性质 B
$13\sim 16$	$20$	$5000$	$2\times 10^5$	$5000$	无
$17\sim 22$	$30$	$2\times 10^5$	$10^6$	$2\times 10^5$	无

特殊性质 A：保证所有 $S$ 只包含左括号。

特殊性质 B：保证所有 $S$ 本身都是合法括号序列前缀。