题目描述

对于一个长度为 $2N$，由 $N$ 个 + 和 $N$ 个 - 组成的字符串 $s$，我们考虑如下问题，并将其答案记作 $p(s)$。

在数轴上 $x=1,2,3,\ldots,2N$ 的位置上排列着 $2N$ 个小球，其中 $N$ 个小球带有 $+1$ 的电荷，其余 $N$ 个小球带有 $-1$ 的电荷。小球的电荷排列方式由 $s$ 给出，$s$ 的第 $i$ 个字符为 + 时，表示 $x=i$ 处放置一个带 $+1$ 电荷的小球，为 - 时，表示 $x=i$ 处放置一个带 $-1$ 电荷的小球。

每个小球会按照以下规则同时开始运动。数轴上数值较小的方向称为左，数值较大的方向称为右。

• 对于每个小球，在每一时刻，$F$ 按如下公式计算： $F = \lbrace$（自身左侧所有小球的电荷总和）$-$（自身右侧所有小球的电荷总和）$\rbrace \times$（自身的电荷）
• 每个小球在每一时刻，如果 $F$ 为正则以每秒 $1$ 的速度向右移动，$F$ 为负则向左移动。
• 若同一时刻同一坐标上同时存在带 $+1$ 电荷和 $-1$ 电荷的小球，则两者相互抵消并消失。

此时，所有小球从开始运动到消失为止所移动距离（消失位置与初始位置的绝对值之差）的总和是多少？

给定一个长度为 $2N$，由 +、-、? 组成的字符串 $T$。将 $T$ 中的 ? 替换为 + 或 -，使得最终得到的字符串 $s$ 恰好有 $N$ 个 + 和 $N$ 个 -。对于所有可能的 $s$，求 $\sum p(s)$，并对 $998244353$ 取模。

在给定的约束和运动规则下，可以保证所有小球在有限时间内全部消失，且只要小球未消失，其 $F$ 的值不会为 $0$，不会出现三球及以上同时位于同一坐标的情况，且 $p(s)$ 一定为整数。

输入格式

输入通过标准输入给出。

$N$ $T$

输出格式

输出 $\sum p(s)$ 对 $998244353$ 取模的结果。

样例 1

输入

2
+??-

输出

6

样例 2

输入

17
??????????????????????????????????

输出

285212526

说明/提示

约束

• $1\leq N\leq 3000$
• $N$ 为整数
• $|T|=2N$
• $T$ 的每个字符为 +、- 或 ?，且 + 和 - 的数量均不超过 $N$

样例解释 1

从 $T$ 可以得到的字符串 $s$ 有 ++-- 和 +-+-。对于 ++--，开始运动时每个小球左右的电荷总和及 $F$ 的值如下图所示。 因此，$x=1,2$ 的小球向右，$x=3,4$ 的小球向左运动。在这种情况下，每个小球之后都不会改变运动方向，$x=2,3$ 的小球将在 $0.5$ 秒后于 $x=2.5$ 相遇消失，$x=1,4$ 的小球将在 $1.5$ 秒后于 $x=2.5$ 相遇消失。在此期间，$x=2,3$ 的小球各自移动 $0.5$，$x=1,4$ 的小球各自移动 $1.5$，因此 $p(\texttt{++--})=4$。同理可得 $p(\texttt{+-+-})=2$，所以所求 $p(s)$ 的总和为 $6$。

样例解释 2

请输出 $p(s)$ 的总和对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译