T1 括号问号

题目信息

时间限制: 1s

空间限制: 512M

输入文件: bracket.in

输出文件: bracket.out

题目描述

对于一个包含 (,) 和 ? 的字符串 $S$，定义 $f(S)$ 为：将 $S$ 中的每个 ? 分别替换成一个 ( 或 )，可能得到的合法括号串的方案数。

给定长度为 $n$，且只包含 (,) 和 ? 的字符串 $T$，对于所有 $2^n$ 个 $T$ 的子序列串 $T'$（包含空串，不要求连续，并且原串不同位置得到的串分别计算），求 $f(T')$ 之和，对 $998244353$ 取模。

---

合法括号串的定义：

• 空串是合法括号串。
• 如果 $A,B$ 都是合法括号串那么它们前后连接 $AB$ 也是合法括号串。
• 如果 $A$ 是合法括号串那么 在 $A$ 外面包裹一对括号得到 $\mathtt{(}A\mathtt{)}$ 也是合法括号串。
• 一个串是括号串当且仅当它是有限长的并且能用有限步以上几种方式构造出来。

输入格式

第一行一个正整数 $n$。

第二行一个字符串 $T$。

输出格式

输出一行一个整数表示答案。

样例

样例输入 #1

4
(?)?

样例输出 #1

7

样例解释 #1

子序列串	所有方案	方案数
空串		$1$
(		$0$
?
)
?
(?	()	$1$
()
(?
?)
??
)?		$0$
(?)
(??
()?
?)?
(?)?	(())	$1$

样例输入 #2

50
???)??)?(?)(?(??)????(?)?))?)((?()??(??))(()()((?(

样例输出 #2

827536427

数据范围与提示

对于所有数据，有：

• $1 \le n \le 5000$
• $T$ 的长度为 $n$，且只由 ( ) 和 ? 组成。

测试点编号	特殊性质
$1 \sim 2$	$n \le 6$
$3 \sim 4$	$n \le 20$
$5 \sim 6$	$n \le 50$
$7 \sim 8$	$n \le 500$
$9 \sim 10$	无