这是这个问题的简单版本。唯一的区别是 $$$n$$$ 的限制 - 输入字符串的长度。在此版本中,$$$1 \leq n \leq 2000$$$。第二级别比赛中不提供此挑战的硬版本。
让我们定义一个正确的括号序列及其深度,如下所示:
- 空字符串是深度 $$$0$$$ 的正确括号序列。
- 如果“s”是深度为 $$$d$$$ 的正确括号序列,则“(s)”是深度为 $$$d + 1$$$ 的正确括号序列。
- 如果“s”和“t”都是正确的括号序列,则它们的串联“st”是正确的括号序列,其深度等于 $$$s$$$ 和 $$$t$$$ 的最大深度。
对于(不一定正确的)括号序列 $$$s$$$,我们将其深度定义为通过从 $$$s$$$ 中删除一些字符(可能为零)而产生的任何正确括号序列的最大深度。例如:括号序列 $$$s = $$$"())(())" 的深度为 $$$2$$$,因为通过删除第三个字符,我们获得了深度为 $$$2$$$ 的正确括号序列“()(())”。
给定一个字符串 $$$a$$$ 仅包含字符 '(', ')' 和 '?'。考虑通过替换所有字符 '?' 获得的所有(不一定正确)括号序列在 $$$a$$$ 中通过“(”或“)”。计算所有这些括号序列的所有深度的总和。由于这个数字可能很大,请对 $$$998244353$$$ 求模。
只有解决了该问题的简单版本和困难版本,才能在第一部分中对这个问题进行黑客攻击。
输入
唯一一行包含仅由“(”、“)”和“?”组成的非空字符串。字符串的长度最多为$$$2000$$$。
输出
在一行中打印对 $$$998244353$$$ 取模的答案。
示例
输入 #1
??
输出 #1
1
输入 #2
(?(?))
输出 #2
9
注意
在第一个测试用例中,我们可以通过替换所有字符 '?' 来获得 $$$4$$$ 括号序列与“(”或“)”:
- "(("。其深度为 $$$0$$$;
- “))”。它的深度是$$$0$$$;
- ")("。其深度为 $$$0$$$;
- “()”。其深度为$$$1$$$。
所以,答案是 $$$1 = 0 + 0 + 0 + 1$$$。
在第二个测试用例中,我们可以通过替换所有字符 '?' 来获得 $$$4$$$ 括号序列与“(”或“)”:
- “(((())”。其深度为$$$2$$$;
- “()()))”。其深度为$$$2$$$;
- “((()))”。其深度为$$$3$$$;
- “()(())”。它的深度是$$$2$$$。
所以,答案是 $$$9 = 2 + 2 + 3 + 2$$$。