作为 RUN 镇的镇长，你正在计划建造一个新的村庄。该村庄由房屋和连接两座不同房屋的双向道路组成。道路的组织方式使得没有两条道路连接同一对房屋。换句话说，该村庄可以被视为一个简单图，其中房屋对应顶点，道路对应双向边。注意，村庄可能是非连通的。

你希望你的村庄尽可能简单。因此，对于任意两座不同的房屋 $i$ 和 $j$，从房屋 $i$ 到房屋 $j$ 的简单路径数量最多为 $K$ 条。

设 $N$ 为房屋的数量。村庄的得分为：

$$\prod_{1 \le i < j \le N} A_{f(i,j)}$$

其中 $f(i, j)$ 是从房屋 $i$ 到房屋 $j$ 的简单路径数量。

虽然房屋的数量尚未确定，但已知它将是一个介于 $2$ 到 $M$ 之间的整数。你需要计算对于每个从 $2$ 到 $M$ 的 $N$，所有可能的 $N$ 座房屋村庄的得分之和。

由于答案可能很大，请输出它们对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含两个空格分隔的整数 $M$ 和 $K$。

第二行包含 $K + 1$ 个空格分隔的整数 $A_0, \dots, A_K$。

• $2 \le M \le 100\,000$
• $0 \le K \le 3$
• $1 \le A_i < 998\,244\,353$ ($0 \le i \le K$)

输出格式

对于每个从 $2$ 到 $M$ 的 $N$，输出所有可能的 $N$ 座房屋村庄的得分之和，对 $998\,244\,353$ 取模。答案之间应以空格分隔。注意 $998\,244\,353 = 119 \cdot 2^{23} + 1$ 是一个质数。

样例

样例输入 1

4 0
2

样例输出 1

2 8 64

样例输入 2

5 1
3 4

样例输出 2

7 327 96721 169832849

样例输入 3

6 2
5 6 7

样例输出 3

11 1566 3000672 306031599 466869291

样例输入 4

7 3
8 9 10 11

样例输出 4

17 5427 31856976 326774674 449014006 997476587