AT_awtf2026algo_c.Count by Descents

Define the score of a sequence of length $N$, $x=(x_1,x_2,\ldots,x_N)$, as $\prod_{1 \leq i \leq N} (i+x_i)$.

You are given a strictly increasing sequence of non-negative integers of length $N$, $A=(A_1,A_2,\ldots,A_N)$.

Solve the following problem for each $d=0,1,\ldots,N-1$.

• Consider the sequences $x$ obtained by rearranging the elements of $A$ such that there are exactly $d$ indices $i$ with $x_i>x_{i+1}$. Find, modulo $998244353$, the sum of the scores over all such sequences.

定义长度为 $N$ 的序列 $x=(x_1,x_2,\ldots,x_N)$ 的得分为 $\prod_{1 \leq i \leq N} (i+x_i)$。

给定一个长度为 $N$ 的严格递增的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$。

对每个 $d=0,1,\ldots,N-1$，求解以下问题：

• 考虑所有由 $A$ 的元素重排得到的序列 $x$，其中恰好有 $d$ 个下标 $i$ 满足 $x_i>x_{i+1}$。求所有此类序列的得分之和，并对 $998244353$ 取模。

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

For each $d=0,1,\ldots,N-1$ in this order, output the answer.

按 $d=0,1,\ldots,N-1$ 的顺序，对每个 $d$ 输出答案。

Sample 1 Explanation:
The permutations and scores corresponding to each $d$ are as follows.

• $d=0$:
  • $x=(0,1)$: the score is $(1+0) \times (2+1)=3$
• $d=1$:
  • $x=(1,0)$: the score is $(1+1) \times (2+0)=4$

Sample 2 Explanation:
The permutations and scores corresponding to each $d$ are as follows.

• $d=0$:
  • $x=(0,1,2)$: the score is $(1+0) \times (2+1) \times (3+2)=15$
• $d=1$:
  • $x=(0,2,1)$: the score is $(1+0) \times (2+2) \times (3+1)=16$
  • $x=(1,0,2)$: the score is $(1+1) \times (2+0) \times (3+2)=20$
  • $x=(1,2,0)$: the score is $(1+1) \times (2+2) \times (3+0)=24$
  • $x=(2,0,1)$: the score is $(1+2) \times (2+0) \times (3+1)=24$
• $d=2$:
  • $x=(2,1,0)$: the score is $(1+2) \times (2+1) \times (3+0)=27$

Constraints

• $2 \leq N \leq 80$
• $0 \leq A_1 < A_2 < \cdots < A_N < 998244353$
• All input values are integers.

样例 1 解释：
对应每个 $d$ 的排列及其得分如下。

• $d=0$：
  • $x=(0,1)$：得分为 $(1+0) \times (2+1)=3$
• $d=1$：
  • $x=(1,0)$：得分为 $(1+1) \times (2+0)=4$

样例 2 解释：
对应每个 $d$ 的排列及其得分如下。

• $d=0$：
  • $x=(0,1,2)$：得分为 $(1+0) \times (2+1) \times (3+2)=15$
• $d=1$：
  • $x=(0,2,1)$：得分为 $(1+0) \times (2+2) \times (3+1)=16$
  • $x=(1,0,2)$：得分为 $(1+1) \times (2+0) \times (3+2)=20$
  • $x=(1,2,0)$：得分为 $(1+1) \times (2+2) \times (3+0)=24$
  • $x=(2,0,1)$：得分为 $(1+2) \times (2+0) \times (3+1)=24$
• $d=2$：
  • $x=(2,1,0)$：得分为 $(1+2) \times (2+1) \times (3+0)=27$

约束条件

• $2 \leq N \leq 80$
• $0 \leq A_1 < A_2 < \cdots < A_N < 998244353$
• 所有输入值均为整数。