AT_wtf22_day2_d.Cat Jumps

给定一个正整数序列 $A_1, A_2, \cdots, A_N$。定义 $S = N + \sum_{1 \leq i \leq N} A_i$。

猫 Snuke 拥有 $S$ 张卡片。每张卡片上写有一个整数，分别为 $A_1, A_2, \cdots, A_N, -1, \cdots, -1$。特别地，写有 $-1$ 的卡片共有 $\sum_{1 \leq i \leq N} A_i$ 张。

Snuke 现在位于数轴上坐标为 $0$ 的位置。接下来，它将进行 $S$ 次如下操作：

• 设 Snuke 当前所在位置的坐标为 $x$。从持有的卡片中选择一张并丢弃。设丢弃的卡片上的数为 $v$，则跳跃到坐标为 $x + v$ 的位置。如果跳跃后的坐标为 $0$，则获得 $1$ 枚硬币。

对于每个 $k = 1, 2, \cdots, N$，求 Snuke 恰好获得 $k$ 枚硬币的跳跃序列有多少种，结果对 $998244353$ 取模。

注意计数的是跳跃序列。也就是说，如果两张卡片上的数相同，则丢弃它们的操作被视为相同的。

输入通过标准输入给出，格式如下：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输出 $N$ 行。第 $i$ 行输出 $k = i$ 时的答案。

约束条件

• $1 \leq N \leq 5000$
• $1 \leq A_i \leq 5000$
• 输入的所有值均为整数。

样例解释 1

例如，跳跃序列 $(-1, +1, +1, -1)$ 是可能的。此时，Snuke 的坐标变化为 $0 \to -1 \to 0 \to 1 \to 0$，并获得 $2$ 枚硬币。以下是所有可能的跳跃序列及其对应的硬币数量：

• $(-1, -1, +1, +1)$：$1$ 枚
• $(-1, +1, -1, +1)$：$2$ 枚
• $(-1, +1, +1, -1)$：$2$ 枚
• $(+1, -1, -1, +1)$：$2$ 枚
• $(+1, -1, +1, -1)$：$2$ 枚
• $(+1, +1, -1, -1)$：$1$ 枚

翻译由 DeepSeek V3 完成