分数: 400 点
问题陈述
给你一个非空字符串 S 组成 (, ),和 ?.
有 2^x 通过替换每个来获取新字符串的方法 ? in S 与 ( 和 ),其中 x 是出现的次数 ? in S。 其中,求数,取模 998244353,产生的方法 括号字符串.
如果满足以下条件之一,则称字符串为括号字符串。
- 这是一个空字符串。
- 这是一个串联
(, A,和),对于某些括号字符串 A. - 这是一个串联 A 和 B,对于一些非空括号字符串 A 和 B.
约束
- S 是一个最大长度的非空字符串 3000 组成
(,),和?.
输入
输入由标准输入按以下格式给出:
S
输出
打印答案。
示例输入 1
(???(?
示例输出 1
2
更换 S 与 ()()() or (())() 产生一个括号字符串。
其他替换不会产生括号字符串,因此 2 。
示例输入 2
)))))
示例输出 2
0
示例输入 3
??????????????(????????(??????)?????????(?(??)
示例输出 3
603032273
打印计数模数 998244353.