题目描述

去年四省赛在L题的位置出了一道跟括号序列相关的题，卡住了无数队伍，今年选拔赛在同样的位置复现一下，看有没有队伍能开出来这道题呢。

众所周知，括号匹配的题一般要用栈来进行，在天梯赛没做出来括号匹配模板题后，热爱编译原理的小明手搓了一个处理括号的编译器，该编译器双栈并行，很容易出错。就在此时，编辑器接收到了一段“括号脚本”——一个只包含$"( "$和$") "$的序列。为了保证脚本在两条独立的通道（通道 H 和通道 G）都能正确执行，必须将每个括号打上 “H” 或 “G” 的标记，要求:

• 按顺序提取所有标记为$H$的括号到一个序列中，该序列应该是一个合法的括号序列。
• 按顺序提取所有标记为$G$的括号到一个序列中，该序列应该是一个合法的括号序列。

“同一对括号”如果标记不同，或“不同位置的括号”标记方式不同，都被视作不同的执行计划。小明想知道，对于给定的括号脚本，一共有多少种合法的标记方案。

输入格式

输入一行，包含一个由 "("和 ")"构成的字符串 A ($1 \le |A| \le 1000$)。

输出格式

输出一行一个整数，合法的标记方案数。由于答案可能很大，所以你只需要输出答案对$998244353$取
模后的结果即可。

样例

(())

6

提示

合法的标记方式有：HGGH，HGHG，GHGH，GHHG，HHHH，GGGG，共6种