时空限制

1S/512M

题目描述

给定一个初始区间 $[l, r] = [1, n]$，你需要依次进行 $m$ 次操作。

第 $i$ 次操作给定一个非负整数 $d_i$，表示本步需要使区间的长度减少恰好 $d_i$。每次操作时，你必须在以下两种方式中选择一种执行：

• 方式 a：将左端点向右移动 $d_i$，即令 $l \leftarrow l + d_i$；
• 方式 b：将右端点向左移动 $d_i$，即令 $r \leftarrow r - d_i$。

特别地，当 $d_i = 0$ 时，虽然区间的实际端点没有发生变化，但选择“方式 a”与“方式 b”仍被视为两种不同的操作。

我们用一个长度为 $m$ 的操作序列来记录每一步的选择（序列中每个位置为 a 或 b）。求对于每个 $k = 1, 2, \dots, n$，有多少种不同的操作序列，使得 $m$ 次操作全部完成后，最终的区间恰好收缩为单点 $[k, k]$？

由于方案数可能很大，请将结果对 $998244353$ 取模。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $m$ 个整数 $d_1, d_2, \dots, d_m$。

输出格式

输出一行，包含 $n$ 个整数，相邻两个整数之间用一个空格隔开。其中第 $k$ 个整数表示最终满足 $l = r = k$ 的操作序列数量对 $998244353$ 取模后的值。

样例

样例输入 #1

3 2
1 1

样例输出 #1

1 2 1

样例解释 #1

初始区间为 $[1, 3]$。

• 若要使最终 $l = r = 1$：唯一合法的操作序列为 [b, b]，区间变化过程为 $[1, 3] \to [1, 2] \to [1, 1]$。
• 若要使最终 $l = r = 2$：合法的操作序列有 [a, b]（区间变化为 $[1, 3] \to [2, 3] \to [2, 2]$）和 [b, a]（区间变化为 $[1, 3] \to [1, 2] \to [2, 2]$），共 $2$ 种。
• 若要使最终 $l = r = 3$：唯一合法的操作序列为 [a, a]，区间变化过程为 $[1, 3] \to [2, 3] \to [3, 3]$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le m \le 2000$，$0 \le d_i \le n - 1$。