問題文

1回引くと $0$ 以上 $2^N-1$ 以下の整数がランダムに1つ手に入るガチャがあります．
それぞれの整数が手に入る確率は数列 $A$ によって表され，整数 $i$ が手に入る確率は $\frac{A_i}{S}$ です．
ただし，$S:=\sum_{i=0}^{2^N-1}A_i$ とします．
また，どの整数が手に入るかは毎回独立です．
今までに手に入れた整数全てのビットごとの論理和が初めて $2^N-1$ になるまでこのガチャを引き続けるとき，その回数の期待値を求めてください．
ただし，期待値が既約分数 $\frac{X}{Y}$ で表されるとき $X$ と $YZ$ が $998244353$ を法として合同となる $0$ 以上 $998244352$ 以下の整数 $Z$ を出力してください．
なお，この問題の制約下で期待値が有理数として存在し，上記の整数 $Z$ が一意に定まることが証明できます．

入力

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

• $1 \leq N \leq 18$
• $1 \leq A_i \leq 1000$
• 入力は全て整数

出力

問題文中で定められた方法で期待値を出力してください．
最後に改行してください．

サンプル

1
1 1

2

2
5 2 2 1

665496240

4
803 973 137 881 44 839 756 403 854 70 708 735 364 40 285 686

284708662