给定一个 $n$ 行 $n$ 列的矩阵，你需要计算它的积和式（permanent）。这个矩阵很特殊，几乎所有元素都是 $1$，只有主对角线上的元素被修改了。

给定 $n$ 个整数 $a_i$。你需要计算 $m$ 个矩阵的积和式。第 $i$ 个矩阵的大小为 $n + i - 1$。

在第 $i$ 个矩阵中，$w_{x,y} = a_x$（当 $x = y$ 且 $x \le n$ 时），$w_{x,y} = 0$（当 $x = y$ 且 $x > n$ 时），以及 $w_{x,y} = 1$（当 $x \neq y$ 时）。

结果可能非常大，请输出结果对 $998244353$ 取模后的值。

输入格式

输入包含多组测试数据，以一行 “0 0” 结束。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)。

接下来一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^6$)。

输入文件总大小不超过 $1.2$ MB。

输出格式

对于每组测试数据，输出 $m$ 行，每行包含一个整数，表示第 $i$ 个矩阵的积和式。

样例

样例输入 1

3 2
2 3 3
0 0

样例输出 1

28
46