问题描述

给你一个由 (、) 和 ? 组成的非空字符串。

有 $2^x$ 种方法可以通过替换 $S$ 中的每个 ? 为 ( 或 ) 来获得新字符串。其中 $x$ 是 ? 出现的次数。找出括号匹配的字符串的数量，模 998244353。

如果满足下列条件之一，则称字符串为括号匹配的字符串。

• 它是一个空字符串。
• 它是 (、 $A$ 和 ) 的连接，其中 $A$ 是括号匹配的字符串。
• 它是 $A$ 和 $B$ 的连接，其中 $A$ 和 $B$ 都是括号匹配的字符串。

数据规模

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

输入

输入来自标准输入，格式如下:

$S$

输出

打印答案。

(???(?

2

将 $S$ 替换为 ()()() 或 (())() 将生成括号字符串。其他替换不会产生括号字符串，因此应打印 2。

)))))

0

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

603032273

打印计数模 998244353。