RUN町の町長として、あなたは新しい村を建設しようと計画しています。村は家々と、異なる2つの家を結ぶ双方向の道路で構成されます。道路は、同じ2つの家を結ぶ道路が複数存在しないように配置されます。言い換えれば、村は家を頂点、道路を双方向の辺とする単純グラフとして扱うことができます。なお、村は連結であるとは限りません。

あなたは村を可能な限り単純にしたいと考えています。そのため、任意の異なる2つの家 $i$ と $j$ について、家 $i$ から家 $j$ への単純パスの数は高々 $K$ 本である必要があります。

$N$ を家の数とします。村のスコアは以下のように定義されます。

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

ここで、$f(i, j)$ は家 $i$ から家 $j$ への単純パスの数です。

家の数はまだ決まっていませんが、2以上 $M$ 以下の整数になることがわかっています。$N$ が 2 から $M$ までのそれぞれについて、$N$ 個の家を持つすべての可能な村のスコアの総和を計算してください。答えは非常に大きくなる可能性があるため、998 244 353 で割った余りを出力してください。

入力

1行目に、2つの整数 $M$ と $K$ が空白区切りで与えられます。 2行目に、$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$)

出力

$N$ が 2 から $M$ までのそれぞれについて、$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