美丽括号序列（简单版）

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

合法括号序列的深度递归定义如下：

• 空串的深度为 $0$；
• 若 $s$ 是深度为 $d$ 的合法括号序列，则 $(s)$ 的深度为 $d+1$；
• 两个合法括号序列拼接后的深度为二者深度的最大值。

对于一个不一定合法的括号串 $s$，定义它的深度为：从 $s$ 删除若干字符后，能够得到的合法括号子序列的最大深度。

给定一个只包含 (、) 和 ? 的字符串。把每个 ? 独立替换为左括号或右括号，求所有替换结果的深度之和。答案对 $998244353$ 取模。

输入格式

一行包含一个非空字符串。

输出格式

输出所有替换结果的深度之和对 $998244353$ 取模后的结果。

样例输入 1

??

样例输出 1

1

样例输入 2

(?(?))

样例输出 2

9

数据范围

字符串长度 $1\le n\le2000$，且只包含 (、)、?。

每个测试点独立计分。