给定一个包含 $n$ 个左括号和 $n$ 个右括号的括号序列。设 $S$ 为 $\{1, 2, \dots, 2n\}$ 的一个非空子集。你可以选择 $S$ 中的两个下标（不一定相邻），并交换括号序列中这两个位置的括号。
求有多少个集合 $S$，使得通过重复执行任意次数该操作，能够将原序列变为一个合法的括号序列。由于结果可能非常大，请输出其对质数 $998\,244\,353$ 取模的结果。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 3000$)。
第二行包含一个长度为 $2n$ 的括号字符串，由 '(' 或 ')' 组成。该括号序列包含 $n$ 个左括号和 $n$ 个右括号。
输出格式
输出所有可能的集合 $S$ 的数量，对 $998\,244\,353$ 取模。
样例
样例输入 1
3 ())(()
样例输出 1
36
样例输入 2
6 ()))(())()((
样例输出 2
1536