En tant que maire de la ville de RUN, vous prévoyez de construire un nouveau village. Le village se compose de maisons et de routes bidirectionnelles reliant deux maisons distinctes. Les routes sont organisées de telle sorte qu'aucune paire de maisons n'est reliée par plus d'une route. En d'autres termes, le village peut être traité comme un graphe simple où les maisons correspondent aux sommets et les routes aux arêtes bidirectionnelles. Notez que le village peut être déconnecté.

Vous souhaitez que votre village soit aussi simple que possible. Par conséquent, pour toutes maisons distinctes $i$ et $j$, il doit y avoir au plus $K$ chemins simples de la maison $i$ à la maison $j$.

Soit $N$ le nombre de maisons. Le score du village est $$\prod_{1 \le i < j \le N} A_{f(i, j)}$$ où $f(i, j)$ est le nombre de chemins simples de la maison $i$ à la maison $j$.

Bien que le nombre de maisons ne soit pas encore déterminé, vous savez qu'il s'agira d'un entier compris entre 2 et $M$. Vous devez calculer la somme des scores pour tous les villages possibles avec $N$ maisons pour chaque $N$ de 2 à $M$. Comme les réponses peuvent être grandes, affichez-les modulo 998 244 353.

Entrée

La première ligne contient deux entiers séparés par des espaces $M$ et $K$. La deuxième ligne contient $K + 1$ entiers séparés par des espaces $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$)

Sortie

Pour chaque $N$ de 2 à $M$, affichez la somme des scores pour tous les villages possibles avec $N$ maisons, modulo 998 244 353. Les réponses doivent être séparées par des espaces. Notez que 998 244 353 = $119 \cdot 2^{23} + 1$ est un nombre premier.

Exemples

Entrée 1

4 0
2

Sortie 1

2 8 64

Entrée 2

5 1
3 4

Sortie 2

7 327 96721 169832849

Entrée 3

6 2
5 6 7

Sortie 3

11 1566 3000672 306031599 466869291

Entrée 4

7 3
8 9 10 11

Sortie 4

17 5427 31856976 326774674 449014006 997476587