时空限制

1S/512M

题目描述

“合法“的括号序列定义如下：

1. 空字符串是合法的；
2. ()、(?、?)、?? 都是合法的；
3. 如果序列 a 是合法的，那么 (a)、(a?、?a)、?a? 也都是合法的；
4. 如果序列 a 和 b 都是合法的，那么 ab 也是合法的。

定义字符串 $X$ 的子序列：删去 $X$ 中任意个（可以是 $0$ 个）字符后，剩下的字符按原有顺序拼接得到的字符串。

如果 $X$ 的第 $i$ 个字符在 $X$ 的子序列 $A$ 中被删除，而在 $X$ 的子序列 $B$ 中没被删除，那么 $A$ 和 $B$ 算作 $X$ 的两个不同子序列。

给定一个仅由 (、)、? 三种字符构成且长度为 $n$ 的字符串 $S$，求 $S$ 的不同子序列中合法的数量，对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $n$ 表示字符串的长度。

第二行包含一个仅由 (、)、? 三种字符构成且长度为 $n$ 的字符串 $S$。

输出格式

输出一个整数，表示 $S$ 的子序列中合法的数量，对 $998244353$ 取模。

样例

样例输入 #1

5
??)??

样例输出 #1

14

样例解释 #1

共有 $14$ 个合法子序列：空串；$\{1,2\}=$??；$\{1,3\}=$?)；$\{1,4\}=$??；$\{1,5\}=$??；$\{2,3\}=$?)；$\{2,4\}=$??；$\{2,5\}=$??；$\{4,5\}=$??；$\{1,2,3,4\}=$??)?；$\{1,2,3,5\}=$??)?；$\{1,2,4,5\}=$????；$\{1,3,4,5\}=$?)??；$\{2,3,4,5\}=$?)??。

样例输入 #2

8 
?(?()(??

样例输出 #2

88

数据规模

对于 $30\%$ 的数据，$n\leq 20$。

另有 $20\%$ 的数据，字符串仅由 (、) 这两种字符组成。

另有 $20\%$ 的数据，字符串仅由 (、? 这两种字符组成。

对于 $100\%$ 的数据，$1\leq n\leq 500$。数据保证字符串仅由 (、)、? 这三种字符组成。