括号序列计数

题目描述

给定一个由 (、)、? 组成的非空字符串 $S$。

将 $S$ 中的每个 ? 替换为 ( 或 ),共有 $2^x$ 种方式,其中 $x$ 是 $S$ 中 ? 的个数。求其中能得到括号序列的方式数,对 $998244353$ 取模。

所谓括号序列,是指满足以下条件之一的字符串:

• 是空字符串;
• 是 (、某个括号序列 $A$、) 依次连接得到的字符串;
• 是两个非空括号序列 $A$ 和 $B$ 连接得到的字符串。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出答案,即能得到括号序列的方式数对 $998244353$ 取模后的值。

样例

(???(?

2

将 $S$ 替换为 ()()() 或 (())() 都能得到括号序列。

其他替换方式不能得到括号序列,所以应输出 $2$。

)))))

0

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

603032273

数据范围

• $S$ 是由 (、)、? 组成的非空字符串,长度至多为 $3000$。