身為 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