Said no more counting dollars. We'll be counting stars.

English Statement

题目描述

$\texttt{__int128}$ 皇帝有一个数组 $a_1, \ldots, a_n$，数组由 非负 整数组成。有一个光标初始位于位置 $p$，满足 $1 \leq p \leq n$。

$\texttt{__int128}$ 皇帝能够在数组 $a$ 上操作，每个操作可以选择执行以下二者之一：

• 如果 $p > 1$，则让 $a_p \leftarrow a_p + 1$，然后 $p \leftarrow p - 1$。
• 如果 $p < n$，则让 $a_p \leftarrow a_p - 1$，然后 $p \leftarrow p + 1$。

对给定的数组 $a$ 和初始光标位置 $p$，$\texttt{__int128}$ 皇帝可以在 $a$ 上进行任意次操作，要求最终光标回到 $p$，生成某个新的 非负 整数组 $b$。对每个 $1 \leq p \leq n$，他希望你计算所有可能得到的不同的非负整数组 $b$ 的数量。答案对 $998244353$ 取模。

注意操作过程中的 $a_i$ 可以 小于 $0$。

输入格式

输入的第一行包含一个整数 $n$。

输入的第二行包含 $n$ 个整数 $a_1, \ldots, a_n$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示若初始 $p = i$，可能得到的非负整数组 $b$ 的数量，对 $998244353$ 取模后的结果。

3
1 2 1

5 7 6

在 $p = 1$ 时，可能得到的不同非负整数组依次如下：

• $[1, 2, 1]$，光标不进行任何移动；
• $[0, 3, 1]$，一种可能的光标移动方式为 $1 \to 2 \to 1$；
• $[0, 2, 2]$，一种可能的光标移动方式为 $1 \to 2 \to 3 \to 2 \to 1$；
• $[0, 1, 3]$，一种可能的光标移动方式为 $1 \to 2 \to 3 \to 2 \to 3 \to 2 \to 1$；
• $[0, 0, 4]$，一种可能的光标移动方式为 $1 \to 2 \to 3 \to 2 \to 3 \to 2 \to 3 \to 2 \to 1$。

在 $p = 2$ 时，可能得到的不同非负整数组有 $[0, 0, 4]$，$[0, 1, 3]$，$[0, 2, 2]$，$[0, 3, 1]$，$[1, 0, 3]$，$[1, 1, 2]$ 和 $[1, 2, 1]$。

在 $p = 3$ 时，可能得到的不同非负整数组有 $[0, 0, 4]$，$[0, 1, 3]$，$[0, 2, 2]$，$[1, 0, 3]$，$[1, 1, 2]$ 和 $[1, 2, 1]$。

5
2 6 3 0 7

613 813 820 799 648

7
1 3 4 2 0 1 5

3060 4915 5161 5166 5118 4847 3862

限制与约定

本题采用捆绑测试，各个子任务之间开启所有合理的子任务依赖。

对于所有数据，保证 $1 \leq n \leq 8000$，$0 \leq a_i \leq 5\cdot 10^8$。

时间限制： $\texttt{4s}$

空间限制： $\texttt{1GB}$