[R8F]括号子序列 - 代码源竞赛平台

时空限制

1S/512M

题目描述

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

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

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

如果 XX 的第 ii 个字符在 XX 的子序列 AA 中被删除，而在 XX 的子序列 BB 中没被删除，那么 AA 和 BB 算作 XX 的两个不同子序列。

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

格式

输入格式

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

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

输出格式

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

样例

样例输入 #1

5
??)??

样例输出 #1

14

样例解释 #1

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

样例输入 #2

8 
?(?()(??

样例输出 #2

88

数据规模

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

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

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

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