Имеется несколько видов драгоценных камней, при этом существует $a_k$ видов камней весом $k$. Вы хотите узнать для каждого $w \le n$, сколько существует способов составить ожерелье из камней так, чтобы в ожерелье было не менее $2$ камней, любые два соседних камня принадлежали к разным видам, а суммарный вес всех камней в ожерелье был равен $w$. Ответ выведите по модулю $998244353$.

Примечание:

• Первый и последний камни в ожерелье также должны принадлежать к разным видам.
• Если два варианта можно совместить друг с другом путем поворота или отражения, они все равно считаются различными вариантами.

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

В первой строке введено целое положительное число $n$.

В следующей строке введено $n$ чисел, где $k$-е число обозначает $a_k$.

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

Выведите одну строку, содержащую $n + 1$ число, представляющих количество способов для $w=0, 1, \dots, n$ соответственно.

Примеры

Пример 1

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

5
2 1 0 1 0

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

0 0 2 4 8 12

Примечание 1

Следующие обозначения можно считать порожденными поворотами:

$$ 2:[1,1']\times 2\\ 3:[1,2]\times 2,[1',2] \times 2\\ 4:[1,1',1,1'] \times 2,[1,1',2]\times 3,[1',1,2]\times 3\\ 5:[1,4]\times 2, [1',4]\times 2, [1,1',1,2]\times 4, [1',1,1',2]\times 4 $$

Пример 2

См. прилагаемые файлы.

Ограничения

Для $100\%$ данных гарантируется, что $2 \le n \le 10^5, 0 \le a_i < 998244353$.