Как мэр города RUN, вы планируете построить новую деревню. Деревня состоит из домов и двусторонних дорог, соединяющих две различные пары домов. Дороги организованы таким образом, что никакие две дороги не соединяют одну и ту же пару домов. Иными словами, деревню можно рассматривать как простой граф, где дома соответствуют вершинам, а дороги — двусторонним ребрам. Заметьте, что деревня может быть несвязной.

Вы хотите, чтобы ваша деревня была как можно проще. Поэтому для любых двух различных домов $i$ и $j$ должно существовать не более $K$ простых путей из дома $i$ в дом $j$.

Пусть $N$ — количество домов. Оценка деревни равна $$\prod_{1 \le i < j \le N} A_{f(i, j)},$$ где $f(i, j)$ — количество простых путей из дома $i$ в дом $j$.

Хотя количество домов еще не определено, вы знаете, что оно будет целым числом от $2$ до $M$. Вам необходимо вычислить сумму оценок для всех возможных деревень с $N$ домами для каждого $N$ от $2$ до $M$. Поскольку ответы могут быть большими, выводите их по модулю $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$)

Выходные данные

Для каждого $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