题目描述

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

括号序列定义如下：

• 空字符串；
• 存在某个括号序列 $A$，将 (、$A$、) 按顺序连接得到的字符串；
• 存在某些非空括号序列 $A, B$，将 $A, B$ 按顺序连接得到的字符串。

输入格式

输入为标准输入，格式如下：

$S$

输出格式

请输出答案。

样例 1

输入

(???(?

输出

2

样例 2

输入

)))))

输出

0

样例 3

输入

??????????????(????????(??????)?????????(?(??)

输出

603032273

说明/提示

限制条件

• $S$ 是一个长度不超过 $3000$ 的非空字符串，仅由 (、)、? 组成。

样例解释 1

将 $S$ 替换为 ()()() 或 (())() 时，可以得到括号序列。除此之外，没有其他替换方式能得到括号序列，因此输出 $2$。

样例解释 3

请输出对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译