题目描述

有一个长度为 $N$ 的圆周。在圆周上的某个固定点，从该点顺时针前进距离 $x$ 的位置，称为坐标 $x$ 的点。

对于每个整数 $i$（$0 \leq i \leq N-1$），在坐标 $i+0.5$ 处有一只老鼠。

すぬけ君现在要进行 $N-1$ 次扔奶酪的操作。具体来说，以下操作会重复 $N-1$ 次：

• 随机选择一个整数 $y$（$0 \leq y \leq N-1$）。其中，选择 $y=i$ 的概率为 $A_i\%$。每次选择都是独立的。
• 然后，从坐标 $y$ 处扔出奶酪。奶酪会沿着圆周顺时针移动。当奶酪经过有老鼠的位置时，会发生以下情况：
  • 如果该老鼠之前没有吃过奶酪：
    • 以 $1/2$ 的概率吃掉奶酪，被吃掉的奶酪就会消失。
    • 以 $1/2$ 的概率什么都不发生。
  • 如果该老鼠之前已经吃过奶酪：
    • 什么都不发生。
• 奶酪会一直沿着圆周移动，直到被某只老鼠吃掉为止。

经过 $N-1$ 次扔奶酪后，恰好只剩下 $1$ 只老鼠没有吃过奶酪。对于每个 $k=0,1,\cdots,N-1$，请计算坐标 $k+0.5$ 处的老鼠最终没有吃到奶酪的概率，并对 $998244353$ 取模。

概率 $\bmod\ 998244353$ 的定义：可以证明，所求概率一定是有理数。此外，在本题的约束下，将其表示为最简分数 $\frac{P}{Q}$ 时，$Q \not\equiv 0 \pmod{998244353}$ 也成立。因此，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

输入格式

输入为以下格式，从标准输入读取：

$N$ $A_0$ $A_1$ $\cdots$ $A_{N-1}$

输出格式

请输出每个 $k=0,1,\cdots,N-1$ 的答案，用空格分隔，输出一行。

样例 1

输入

2
0 100

输出

665496236 332748118

样例 2

输入

2
50 50

输出

499122177 499122177

样例 3

输入

10
1 2 3 4 5 6 7 8 9 55

输出

333507001 91405664 419217284 757959653 974851434 806873643 112668439 378659755 979030842 137048051

说明/提示

约束

• $1 \leq N \leq 40$
• $0 \leq A_i$
• $\sum_{0 \leq i \leq N-1} A_i = 100$
• 输入的所有值都是整数

样例解释 1

必然会选择 $y=1$。从这里扔出奶酪时，会发生以下情况：

• 以 $1/2$ 的概率，坐标 $1.5$ 的老鼠吃掉奶酪。
• 以 $1/4$ 的概率，坐标 $0.5$ 的老鼠吃掉奶酪。
• 以 $1/8$ 的概率，坐标 $1.5$ 的老鼠吃掉奶酪。
• 以 $1/16$ 的概率，坐标 $0.5$ 的老鼠吃掉奶酪。
• $\vdots$ 最终，这块奶酪被坐标 $0.5, 1.5$ 的老鼠吃掉的概率分别为 $1/3, 2/3$。 因此，最终没有吃到奶酪的概率分别为 $2/3, 1/3$。

由 ChatGPT 4.1 翻译