题目描述

長さ $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$ にいるネズミが最終的にチーズを食べていない確率を $\bmod\ 998244353$ で求めてください．

確率 $\bmod\ 998244353$ の定義 求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $\frac{P}{Q}$ で表した時、$Q\ \neq\ 0\ \pmod{998244353}$ となることも証明できます。 よって、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ &lt\ 998244353 $ を満たす整数 $R$ が一意に定まります。 この $R$ を答えてください。

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

各 $k=0,1,\cdots,N-1$ に対する答えを，空白区切りで一行に出力せよ．

题目大意

给定一个长度为 $n$ 的圆周。在这个圆周上，点的坐标为 $x$ 表示以某个固定点开始沿顺时针方向的距离为 $x$。

对于任意 $0 \le i \le n-1$，有一只坐标为 $i + 0.5$ 的老鼠。

Snuke 会投掷 $n-1$ 次奶酪。具体地说，他会重复以下步骤 $n-1$ 次：

• 随机选择一个 $0$ 到 $n-1$ 间的整数 $y$，$y=i$ 的概率为百分之 $a_i$。任意两次选择是独立的。
• 随后，从 $y$ 位置投掷奶酪。奶酪会以顺时针方向沿圆周前进。当奶酪遇到一只老鼠时，会发生以下事件：
  • 如果老鼠没有吃过奶酪：
    • 其会以 $1/2$ 的概率吃掉奶酪。奶酪就此消失。
    • 其会以 $1/2$ 的概率什么都不做。
  • 如果老鼠吃过了奶酪：
    • 其会什么都不做。
• 奶酪会一直前进，直到被某只老鼠吃掉。

投掷完 $n-1$ 次奶酪后，会有恰好一只老鼠没有吃奶酪。对于每个整数 $0\le k\le n-1$，请输出坐标为 $k + 0.5$ 的老鼠没有吃奶酪的概率模 $998244353$ 的值。

能够证明题目中的每个概率总能被表示为一个分母不为 $0$ 的分数。设 $\frac PQ$ 为最简分数，则 $\frac PQ$ 模 $998244353$ 的值为整数 $0\le R < 998244353$ 满足 $R\times Q \equiv P \pmod{998244353}$。

$1\le n \le 40,\ 0\le a_i,\ \sum_{0\le i \le n-1}a_i = 100$。

2
0 100

665496236 332748118

2
50 50

499122177 499122177

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$
• 入力される値はすべて整数である

Sample Explanation 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$ になります．