题目描述

给定一个非空字符串包含 (，) 和 ?。

其中 ? 需要用 ( 或者 ) 替换掉，求替换后的字符串是合法的括号串的方案数对 $998244353$ 取模的值。

其中合法括号串满足以下条件之一：

• 该串是空串，那么该串是合法括号串；

• 如果 $A$ 是合法括号串，那么 ($A$) 是合法括号串；

• 如果 $A$，$B$ 是合法括号串，那么 $AB$ 也是合法括号串。

输入格式

输入一个字符串 $S$ 。

输出格式

输出题目要求的答案，方案数对 $998244353$ 取模。

样例 #1

样例输入 #1

(???(?

样例输出 #1

2

只有两种置换方法是合法的： ()()() 和 (())() 。

样例 #2

样例输入 #2

)))))

样例输出 #2

0

样例 #3

样例输入 #3

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

样例输出 #3

603032273

提示

对于 $100\%$ 的数据：

• $S$ 只会有 (, ), ? 三种字符
• $|S| \le 3000$