Electro Master

I might be wrong.

考虑一个由四种微观粒子构成的系统：正负 A 子 $\text{a}^+,\text{a}^-$，正负 B 子 $\text{b}^+,\text{b}^-$。 一开始，一条直线上放置了 $n$ 个 A 子；然后以某种方式给粒子以初速度，使得带正电荷的粒子向左，反之则向右运动。我们忽略粒子之间的相互作用，认为粒子在加速后速率一定，且均沿直线运动。 当两个粒子相撞时，粒子会反弹，沿着相反的方向继续运动。同时满足如下的变换规律： - 若两种粒子的电荷相同，则无事发生； - 若两种粒子的电荷不同，则改变成另一种同电荷的粒子。 例如：$\text{a}^-$ 和 $\text{b}^+$ 相撞后，$\text{a}^-$ 会变成 $\text{b}^-$，$\text{b}^+$ 会变成 $\text{a}^+$，并各自沿着相反的方向运动。 定义一种摆放方式的权值为，经过足够长的时间后，在左侧收集到的 B 子个数。 现在已经确定了一些 A 子的正负性，剩下的 A 子可能带正电，也有可能带负电。请求出对于所有可能方案的权值之和。 你需要将答案对 $998\,244\,353$ 取模。

输入一行一个长为 $n$ 的字符串 $s$，代表从左到右的 A 子的正负性。具体而言： - 若 $s_i$ 为 `+`，则第 $i$ 个 A 子带正电； - 若 $s_i$ 为 `-`，则第 $i$ 个 A 子带负电； - 若 $s_i$ 为 `?`，则第 $i$ 个 A 子可能带正电，也可能带负电。

输出一行一个数，代表答案对 $998\,244\,353$ 取模后的结果。

+?+-

1

??+-?-+

11

-????-?+?--????

2523

#### 样例 1 解释 有两种可能的填法：`+++-` 或 `+-+-`。其权值分别为 $0,1$，所以最终的答案即为 $1$。 ### 数据规模与约定 对于所有数据，保证 $1\le n\le 2000$，$s_i\in \{\texttt{+},\texttt{-},\texttt{?}\}$。 | # | $n\le $ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | | 0 | - | 样例 | $0$ | | 1 | $100$ | $s$ 中没有 `?` | $10$ | | 2 | $100$ | - | $20$ | | 3 | $300$ | $s$ 中 `?` 不超过 $15$ 个 | $15$ | | 4 | $300$ | - | $20$ | | 5 | - | - | $35$ |