该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

合法括号串的定义：

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

输入格式

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

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

输出格式

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

4
(?)?

7

样例解释 #1

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

827536427

数据范围与提示

对于所有数据，有：

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