2446: 计数括号序列
[Creator : ]
Description
给定一个非空字符串包含 `(`，`)` 和 `?`。
其中 `?` 需要用 `(` 或者 `)` 替换掉，求替换后的字符串是合法的括号串的方案数对 $ 998244353$ 取模的值。
其中合法括号串满足以下条件之一：
- 该串是空串，那么该串是合法括号串；
- 如果 $A$ 是合法括号串，那么 `(`$A$`)` 是合法括号串；
- 如果 $A$，$B$ 是合法括号串，那么 $AB$ 也是合法括号串。
其中 `?` 需要用 `(` 或者 `)` 替换掉，求替换后的字符串是合法的括号串的方案数对 $ 998244353$ 取模的值。
其中合法括号串满足以下条件之一：
- 该串是空串，那么该串是合法括号串；
- 如果 $A$ 是合法括号串，那么 `(`$A$`)` 是合法括号串；
- 如果 $A$，$B$ 是合法括号串，那么 $AB$ 也是合法括号串。
Input
一行字符串S
- $S$ 是一个长度至多为 $3000$ 的非空字符串，由 `(`,`)`和 `?`组成。
- $S$ 是一个长度至多为 $3000$ 的非空字符串，由 `(`,`)`和 `?`组成。
Output
输入替换后的字符串是合法的括号串的方案数对 $ 998244353$ 取模的值。
Sample Input Copy
(???(?
Sample Output Copy
2
HINT
样例输入2：
)))))
)))))
样例输出2：
0
0
样例输出3：
??????????????(????????(??????)?????????(?(??)
??????????????(????????(??????)?????????(?(??)
样例输出3：
603032273
603032273