题目描述

小明正在研究一种特殊的括号序列。

现在有一个长度为 $n$ 的字符串 $S$，其中每个字符可能是：

• (，表示一个左括号；
• )，表示一个右括号；
• ?，表示一个未知括号。

对于每一个 ?，小明可以将它替换成 ( 或者 )。

经过所有替换后，可以得到许多不同的括号字符串。如果一个字符串满足括号匹配规则，则称它为一个合法括号串。现在请你计算，有多少种替换方式，可以使最终得到的字符串成为合法括号串。

答案可能很大，请输出答案对 $998244353$ 取模后的结果。

输入格式

输入一行一个字符串 $S$。表示初始的括号字符串。

输出格式

输出一个整数，表示可以得到合法括号串的替换方案数。答案需要对 $998244353$ 取模。

样例 #1

(???(?

2

样例解释 #1

对于样例 1：

字符串：(???(? 其中一种替换方式为： ()()()

另一种替换方式为：(())() 这两种方式可以得到合法括号串，因此答案为：2

样例 #2

)))))

0

样例 #3

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

603032273

数据范围

对于 $40\%$ 的数据，满足：$1\le n \le300$

对于 $100\%$ 的数据，满足：$1\le n \le3000$

保证字符串 $S$ 仅由 (、) 和 ? 组成。