Malnar 先生在他的花园里拥有一道由 $n$ 根植物茎组成的篱笆，第 $i$ 根茎的高度为 $A_i$，Malnar 先生知道所有茎的总高度为 $S$。

为了翻新篱笆，Malnar 先生决定将植物修剪到一定高度。由于这些茎很脆弱，每根茎最多只能被修剪一次。此外，Malnar 先生的剪刀技术并不娴熟，为了简化工作，如果他在某个高度 $v$ 修剪了某根茎，那么每一根高度严格大于 $v$ 的相邻茎也必须被修剪到该高度。请注意，Malnar 先生不一定要修剪每一根茎，他可能忘记带剪刀，从而一根也不修剪。

图 I.1 左侧是正确修剪的示例，右侧是错误修剪的示例，禁止在第 2 根与第 3 根，以及第 4 根与第 5 根之间进行此类修剪。

Malnar 先生想知道，对于从 $0$ 到 $S$ 的每一个长度 $X$，他有多少种不同的修剪方式可以得到总长度为 $X$ 的篱笆。如果两道篱笆中存在某根植物的高度不同，则认为这两道篱笆是不同的。他不需要精确的数值，只需要输出结果对 $998\,244\,353$ 取模后的余数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2\,000$)，即篱笆中茎的数量。

第二行包含 $n$ 个整数，其中第 $i$ 个数表示 $A_i$ ($0 \le A_i \le 2\,000$)，即第 $i$ 根茎的高度。

此外，所有高度之和满足 $S \le 2\,000$。

输出格式

输出 $S + 1$ 行，其中第 $i$ 行表示总长度为 $i - 1$ 的篱笆修剪方案数对 $998\,244\,353$ 取模后的余数。

样例

输入 1

4
0 0 1 6

输出 1

1
0
1
1
1
1
1
1

输入 2

3
4 6 0

输出 2

1
0
1
0
1
0
1
0
1
1
1

输入 3

5
1 1 2 1 0

输出 3

1
0
0
0
1
1

说明

第一个样例的说明：在第一个样例中，无法得到总长度为 1 的篱笆。如果我们在高度 0 处修剪第 3 根茎，那么我们也必须在高度 0 处修剪第 4 根茎。同理，如果我们修剪第 4 根茎，我们也必须修剪第 3 根茎。对于从 2 到 7 的所有数字，恰好有一种方法可以达到该长度：长度 2 到 6 通过修剪第 4 根茎实现，长度 7 通过不进行任何修剪实现。总长度为 0 的篱笆可以通过将所有植物修剪到高度 0 来实现。