JOHNKRAM в последнее время изучает теорию графов. Сегодня он столкнулся с такой задачей: дан ориентированный граф без кратных ребер и петель. Требуется найти количество вершин с нулевой входящей степенью после конденсации графа в граф сильно связных компонент.

JOHNKRAM легко решил эту задачу с помощью алгоритма Тарьяна. Однако он заметил, что многие другие пишут код гораздо короче, и, попросив их программы, обнаружил, что они просто выводят $1$ = =. Неужели случайные данные настолько слабы? Он сгенерировал множество случайных ориентированных графов и обнаружил, что ответ действительно всегда равен $1$ = =. Тогда он изменил способ генерации: теперь он генерирует только такие ориентированные графы, в которых размер каждой сильно связной компоненты принадлежит некоторому множеству $S$. В результате ответ сразу стал больше.

Теперь JOHNKRAM отсеял тех, кто писал неверные решения, но он хочет доказать силу своих данных, поэтому он поставил вопрос: для всех помеченных ориентированных графов с $i$ вершинами ($1\leq i\leq n$), в которых размер каждой сильно связной компоненты принадлежит множеству $S$, каково математическое ожидание ответа на предыдущую задачу? Он понял, что не может это доказать, и обратился к вам за помощью.

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

Первая строка содержит одно целое число $n$, максимальное количество вершин в генерируемом ориентированном графе.

Далее следуют $n$ строк, в $i$-й из которых содержится целое число $s_i$. Если $s_i=1$, то $i$ принадлежит множеству $S$, иначе $i$ не принадлежит $S$.

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

Выведите $n$ строк, по одному целому числу в каждой. Число в $i$-й строке — это математическое ожидание ответа для всех помеченных ориентированных графов с $i$ вершинами ($1\leq i\leq n$), в которых размер каждой сильно связной компоненты принадлежит множеству $S$, по модулю $998244353$. Если подходящих ориентированных графов не существует, выведите $0$. Если ожидаемое значение равно $a/b$ (где $a$ и $b$ — взаимно простые положительные целые числа), то выводимое вами целое число $x$ должно удовлетворять условию $bx\equiv a \pmod{998244353}$ и $0\leq x < 998244353$.

Примеры

Пример 1

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

3
1
0
0

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

1
332748119
519087065

Примечание

Для ориентированных графов с $1$ вершиной существует $1$ подходящий граф, в котором ответ равен $1$, поэтому ожидание равно $1$, что по модулю $998244353$ дает $1$.

Для ориентированных графов с $2$ вершинами существует $2$ подходящих графа с ответом $1$ и $1$ подходящий граф с ответом $2$, поэтому ожидание равно $\frac{4}{3}$, что по модулю $998244353$ дает $332748119$.

Для ориентированных графов с $3$ вершинами существует $15$ подходящих графов с ответом $1$, $9$ подходящих графов с ответом $2$ и $1$ подходящий граф с ответом $3$, поэтому ожидание равно $\frac{36}{25}$, что по модулю $998244353$ дает $519087065$.

Ограничения

Для всех тестовых данных $1\leq n\leq 100000$, $0\leq s_i\leq 1$.