Como alcalde de la ciudad RUN, estás planeando construir una nueva aldea. La aldea consiste en casas y caminos bidireccionales que conectan dos casas distintas. Los caminos están organizados de tal manera que no hay dos caminos que conecten el mismo par de casas. En otras palabras, la aldea puede tratarse como un grafo simple donde las casas corresponden a vértices y los caminos corresponden a aristas bidireccionales. Ten en cuenta que la aldea puede estar desconectada.

Quieres que tu aldea sea lo más simple posible. Por lo tanto, para cualquier par de casas distintas $i$ y $j$, debe haber como máximo $K$ caminos simples desde la casa $i$ hasta la casa $j$.

Sea $N$ el número de casas. La puntuación de la aldea es $$\prod_{1 \le i < j \le N} A_{f(i,j)}$$ donde $f(i, j)$ es el número de caminos simples desde la casa $i$ hasta la casa $j$.

Aunque el número de casas aún no está determinado, sabes que será un número entero entre $2$ y $M$. Debes calcular la suma de las puntuaciones para todas las posibles aldeas con $N$ casas para cada $N$ desde $2$ hasta $M$. Dado que las respuestas pueden ser grandes, imprímelas módulo $998\,244\,353$.

Entrada

La primera línea contiene dos enteros separados por espacios $M$ y $K$. La segunda línea contiene $K + 1$ enteros separados por espacios $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$)

Salida

Para cada $N$ desde $2$ hasta $M$, imprime la suma de las puntuaciones de todas las posibles aldeas con $N$ casas, módulo $998\,244\,353$. Las respuestas deben estar separadas por espacios simples. Ten en cuenta que $998\,244\,353 = 119 \cdot 2^{23} + 1$ es un número primo.

Ejemplos

Entrada 1

4 0
2

Salida 1

2 8 64

Entrada 2

5 1
3 4

Salida 2

7 327 96721 169832849

Entrada 3

6 2
5 6 7

Salida 3

11 1566 3000672 306031599 466869291

Entrada 4

7 3
8 9 10 11

Salida 4

17 5427 31856976 326774674 449014006 997476587