题目描述

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

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

合法括号串的定义：

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

输入格式

从文件 bracket.in 中读入数据。

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

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

输出格式

输出到文件 bracket.out 中。

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

样例 1 输入

4
(?)?

样例 1 输出

7

样例 1 解释

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

样例 2 输入

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

样例 2 输出

827536427

样例 3

见选手目录下的 bracket/bracket3.in 与 bracket/bracket3.ans。

该样例满足第 $13\sim16$ 个测试点的限制。

样例 4

见选手目录下的 bracket/bracket4.in 与 bracket/bracket4.ans。

该样例满足第 $17\sim20$ 个测试点的限制。

数据范围

对于所有测试数据，保证：$1\le n\le5000$，$T$ 的长度为 $n$，且只由 (、) 和 ? 组成。

测试点	$n$	特殊性质
$1\sim4$	$\le6$	无特殊性质
$5\sim8$	$\le20$
$9\sim12$	$\le50$
$13\sim16$	$\le500$
$17\sim20$	$\le5000$

共有 $20$ 个测试点，每个测试点独立计 $5$ 分。