Jako burmistrz miasta RUN planujesz budowę nowej wioski. Wioska składa się z domów oraz dwukierunkowych dróg łączących dwie różne pary domów. Drogi są zorganizowane w taki sposób, że żadne dwie drogi nie łączą tej samej pary domów. Innymi słowy, wioskę można traktować jako graf prosty, w którym domy odpowiadają wierzchołkom, a drogi odpowiadają krawędziom dwukierunkowym. Zauważ, że wioska może być niespójna.

Chcesz, aby Twoja wioska była jak najprostsza. Dlatego dla każdych dwóch różnych domów $i$ oraz $j$ powinno istnieć co najwyżej $K$ ścieżek prostych z domu $i$ do domu $j$.

Niech $N$ będzie liczbą domów. Wynik wioski wynosi:

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

gdzie $f(i, j)$ to liczba ścieżek prostych z domu $i$ do domu $j$.

Choć liczba domów nie jest jeszcze ustalona, wiesz, że będzie to liczba całkowita z przedziału od $2$ do $M$. Powinieneś obliczyć sumę wyników dla wszystkich możliwych wiosek z $N$ domami dla każdego $N$ od $2$ do $M$. Ponieważ wyniki mogą być duże, wyprowadź je modulo $998\,244\,353$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $M$ oraz $K$ oddzielone spacją. Druga linia zawiera $K + 1$ liczb całkowitych $A_0, \dots, A_K$ oddzielonych spacjami.

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

Wyjście

Dla każdego $N$ od $2$ do $M$ wyprowadź sumę wyników dla wszystkich możliwych wiosek z $N$ domami, modulo $998\,244\,353$. Odpowiedzi powinny być oddzielone pojedynczymi spacjami. Zauważ, że $998\,244\,353 = 119 \cdot 2^{23} + 1$ jest liczbą pierwszą.

Przykład

Wejście 1

4 0
2

Wyjście 1

2 8 64

Wejście 2

5 1
3 4

Wyjście 2

7 327 96721 169832849

Wejście 3

6 2
5 6 7

Wyjście 3

11 1566 3000672 306031599 466869291

Wejście 4

7 3
8 9 10 11

Wyjście 4

17 5427 31856976 326774674 449014006 997476587