AT_abc312_d [ABC312D] Count Bracket Sequences

给定一个非空字符串 $S$，其中每个字符都是 `(`、`)` 或 `?` 之一。 如果 $S$ 中包含 $x$ 个 `?`，那么将每个 `?` 替换为 `(` 或 `)` 可以得到 $2^x$ 种新的字符串。请你计算，在这些替换方式中，使得新字符串成为**括号序列**的方案数，并输出其对 $998244353$ 取模的结果。 括号序列定义如下： - 空字符串； - 存在某个括号序列 $A$，将 `(`、$A$、`)` 按顺序连接得到的字符串； - 存在某些非空括号序列 $A, B$，将 $A, B$ 按顺序连接得到的字符串。

输入为标准输入，格式如下： > $S$

请输出答案。

## 限制条件 - $S$ 是一个长度不超过 $3000$ 的非空字符串，仅由 `(`、`)`、`?` 组成。 ## 样例解释 1 将 $S$ 替换为 `()()()` 或 `(())()` 时，可以得到括号序列。除此之外，没有其他替换方式能得到括号序列，因此输出 $2$。 ## 样例解释 3 请输出对 $998244353$ 取模的结果。 由 ChatGPT 4.1 翻译