{"raw_statement":[{"iden":"problem statement","content":"Snuke found a random number generator. It generates an integer between $0$ and $2^N-1$ (inclusive). An integer sequence $A_0, A_1, \\cdots, A_{2^N-1}$ represents the probability that each of these integers is generated. The integer $i$ ($0 \\leq i \\leq 2^N-1$) is generated with probability $A_i / S$, where $S = \\sum_{i=0}^{2^N-1} A_i$. The process of generating an integer is done independently each time the generator is executed.\nSnuke has an integer $X$, which is now $0$. He can perform the following operation any number of times:\n\n*   Generate an integer $v$ with the generator and replace $X$ with $X \\oplus v$, where $\\oplus$ denotes the bitwise XOR.\n\nFor each integer $i$ ($0 \\leq i \\leq 2^N-1$), find the expected number of operations until $X$ becomes $i$, and print it modulo $998244353$. More formally, represent the expected number of operations as an irreducible fraction $P/Q$. Then, there exists a unique integer $R$ such that $R \\times Q \\equiv P \\mod 998244353,\\ 0 \\leq R < 998244353$, so print this $R$.\nWe can prove that, for every $i$, the expected number of operations until $X$ becomes $i$ is a finite rational number, and its integer representation modulo $998244353$ can be defined."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 18$\n*   $1 \\leq A_i \\leq 1000$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_0$ $A_1$ $\\cdots$ $A_{2^N-1}$"},{"iden":"sample input 1","content":"2\n1 1 1 1"},{"iden":"sample output 1","content":"0\n4\n4\n4\n\n$X=0$ after zero operations, so the expected number of operations until $X$ becomes $0$ is $0$.\nAlso, from any state, the value of $X$ after one operation is $0$, $1$, $2$ or $3$ with equal probability. Thus, the expected numbers of operations until $X$ becomes $1$, $2$ and $3$ are all $4$."},{"iden":"sample input 2","content":"2\n1 2 1 2"},{"iden":"sample output 2","content":"0\n499122180\n4\n499122180\n\nThe expected numbers of operations until $X$ becomes $0$, $1$, $2$ and $3$ are $0$, $7/2$, $4$ and $7/2$, respectively."},{"iden":"sample input 3","content":"4\n337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355"},{"iden":"sample output 3","content":"0\n468683018\n635850749\n96019779\n657074071\n24757563\n745107950\n665159588\n551278361\n143136064\n557841197\n185790407\n988018173\n247117461\n129098626\n789682908"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}