题目背景

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{?}\}$。