题目描述

小 B 热衷于炒股，这天他花重金买入了一只股票，计划持有 $n$ 天后卖出。

这 $n$ 天中的每一天，股价都会发生变化，每天的变化是如下三种情况之一：

1. 股价上涨，这一天小 B 可以赚 $1$ 万元。
2. 股价保持不动，这一天小 B 不赚也不亏。
3. 股价下跌，这一天小 B 会亏 $1$ 万元。

$n$ 天后小 B 卖出了股票，他想要总结一下这段时间的炒股经历，突然发现自己忘记了一部分天数中的股价变化情况。

但是他记得很清楚的是，赚得最多的时候（可能是最后一天之后，可能是中间的某一天之后，也可能是一开始时），他比一开始一共赚了 $k$ 万元。

小 B 想要还原出每一天的股价变化情况，当然他知道，由于信息不全，可能有很多种方案都是符合要求的。请你求出符合要求的方案一共有多少种。

由于小 B 要进一步分析股价的变化规律，所以他还希望对于每个 $k\in[0,n]$ 都求出答案。

输入格式

第 1 行，一个正整数 $n$。

第 2 行，一个长度为 $n$ 的字符串，由 "+ - 0 ?" 4 种字符组成，描述每一天的股价变化情况。其中 + 表示这一天股价上涨，- 表示这一天股价下跌，0 表示这一天股价不变，? 表示小 B 忘了这一天股价的变化情况。

输出格式

$n+1$ 行，每行一个整数，第 $i$ 行表示 $k=i-1$ 时合法的股价变化情况的种数。

由于答案可能很大，你只需要输出答案对 $998244353$（质数）取模的结果。

样例

样例输入 #1

5
?+0?-

样例输出 #1

2
3
3
1
0
0

样例解释 #1

如下 $2$ 种方案满足 $k=0$：

-+00-
-+0--

如下 $3$ 种方案满足 $k=1$：

0+00-
0+0--
-+0+-

如下 $3$ 种方案满足 $k=2$：

0+0+-
++00-
++0--

如下 $1$ 种方案满足 $k=3$：

++0+-

其余样例见下发文件

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 5000$。