题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \cdots, A_N)$ 和一个整数 $K$。

对于每一个满足 $1 \le X \le K$ 的整数 $X$，请计算以下值：

$$\left(\sum\_{L=1}^{N-1} \sum\_{R=L+1}^{N} (A\_L + A\_R)^X\right) \bmod 998244353$$

输入格式

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

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

输出格式

请输出 $K$ 行。

第 $X$ 行输出 $\left(\sum\_{L=1}^{N-1} \sum\_{R=L+1}^{N} (A\_L + A\_R)^X\right) \bmod 998244353$ 的值。

样例 1

输入

3 3
1 2 3

输出

12
50
216

样例 2

输入

10 10
1 1 1 1 1 1 1 1 1 1

输出

90
180
360
720
1440
2880
5760
11520
23040
46080

样例 3

输入

2 5
1234 5678

输出

6912
47775744
805306038
64822328
838460992

说明/提示

限制条件

• 输入均为整数。
• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 300$
• $1 \le A_i \le 10^8$

样例解释 1

第 $1$ 行输出 $(1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12$。
第 $2$ 行输出 $(1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50$。
第 $3$ 行输出 $(1+2)^3 + (1+3)^3 + (2+3)^3 = 27 + 64 + 125 = 216$。

样例解释 3

请输出对 $998244353$ 取模后的值。

由 ChatGPT 4.1 翻译