题目描述

给定一个长为 $n$ 的序列 $a$，按如下方法计算 $f(x)$：

• $f(0)=1$;
• 当整数 $m\in[1,n]$ 时，$f(m)=a\_m\times (\displaystyle\sum\_{i+j\lt m} f(i)\times f(j))$。

对于每个整数 $i\in[1,n]$，计算 $f(i)$ $\bmod$ $998244353$ 的值。

输入格式

第一行为序列长度 $n$，第二行输入 $n$ 个整数表示序列 $a$。

输出格式

依次输出 $f(1)$，$f(2)$，…，$f(n)$ 对 $998244353$ 取模后的值，相邻两个数之间以单个空格隔开。

样例 1

输入

5
1 2 3 4 5

输出

1 6 48 496 6240

样例 2

输入

3
12345 678901 2345678

输出

12345 790834943 85679169

说明/提示

数据规模与约定

$1\le n\le 2\times 10^5$，$a_i\in[0,998244352]$。