同学们在教室传答案，一点也不方，因为已经传过很多次了；同学们在教室里传答案被逮到了，但问题不大，以前被逮到过很多次了。

全班共有$n$个同学，每次参与传答案的同学都是$n$个同学的一个子集。一学期共$2^n$有次考试，每次考试参与传答案的同学都不完全相同。

老师每次考试有一半的概率记录这次考试参与传答案的同学名单，也有一半的概率当做什么也没发生。到了期末，老师检查一下自己记下的名单，找出每次都参与了传答案的同学，作为这学期的“始作俑者”。特别的，如果老师一学期没有记录任何一次考试的传答案名单，则没有学生是“始作俑者”。

老师对第$i$个学生的惩罚系数是正整数$a_i$。期末抓出始作俑者之后，算出始作俑者人数$x$和最大的惩罚系数$y$，对全班施加的惩罚量$z=xy$。特别的，如果没有学生是始作俑者，惩罚量为0。

求期末惩罚量的期望$E(z)$。为了方便，输出 \(E(z)\times2^{2^n}\mod{998244353}\) ，容易证明，$E(z)\times2^{2^n}$是个整数。

第一行一个整数$n$，表示全班的人数。

第二行$n$个整数$a_1,a_2,\dots,a_n$，是老师对每个学生的惩罚系数。

输出一个整数，表示答案。

样例说明1

先不妨假设第$1,2,3,4$场考试时，参与传答案的同学集合分别是$\emptyset,\{1\},\{2\},\{1,2\}$。

• 始作俑者$=\emptyset$有很多种情况，但惩罚量为$0$。
• 始作俑者$=\{1\}$可以是记录了第$2$场考试，或者第$2,4$两场考试，总概率为$\frac18$；人数为$1$，最大惩罚系数为$1$，所以惩罚量为$1$。
• 始作俑者$=\{2\}$同上。
• 始作俑者$=\{1,2\}$必须是只记录第$4$场考试，概率为$\frac1{16}$；人数为$2$，最大惩罚系数为$1$，所以惩罚量为$2$。

惩罚量期望$E(z)=\frac18\times1+\frac{1}8\times1+\frac1{16}\times2=\frac38$，所以答案是$\frac{3}8\times2^{2^2}=6$。

样例说明2

先不妨假设第$1,2,3,4$场考试时，参与传答案的同学集合分别是$\emptyset,\{1\},\{2\},\{1,2\}$。

• 始作俑者$=\emptyset$有很多种情况，但惩罚量为$0$。
• 始作俑者$=\{1\}$的概率为$\frac{1}8$，惩罚量为$5$。
• 始作俑者$=\{2\}$的概率为$\frac{1}8$，惩罚量为$13$。
• 始作俑者$=\{1,2\}$的概率为$\frac1{16}$，惩罚量为$26$。

惩罚量期望$E(z)=\frac{1}8\times5+\frac{1}8\times13+\frac1{16}\times26=\frac{31}8$，所以答案是$\frac{31}8\times2^{2^2}=62$。

数据规模与约定

对于10%的数据，\(n=2\)；

对于30%的数据，\(n\leq4\)；

对于60%的数据，\(n\leq16\)；

对于100%的数据， \(2\leq n\leq2^{12},\quad 1\leq a_i\leq2^{20}\) ，每组时限2秒。

对于额外100%的数据， \(2\leq n\leq2^{20},\quad 0\leq a_i<998244353\) ，每组时限4秒。