Description

Alice 正在数轴上玩一个单人游戏。

数轴上有 $n$ 个点。每次，玩家选择两个点。这两个点将被移除，并添加它们的中点。当数轴上只剩下一个点时，游戏结束。形式上，如果选择的两个点是 $x_i$ 和 $x_j$，那么在操作后将添加 $\dfrac{x_i+x_j}{2}$。

为了愉快地进行这个游戏，Alice 总是随机选择两个点。

现在 Alice 有一个问题：最后一个点的期望位置在哪里。

可以证明，答案可以表示成 $\dfrac{p}{q}$ 的形式，你只需要输出 $p\cdot q^{-1} \bmod 998\,244\,353$ 的值。

Input Format

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包含 $n$ 个整数 $x_i$ ($0 \le x_1 \le \dots \le x_n < 998\,244\,353$)，表示第 $i$ 个点的位置。

注意，两个点可能在同一位置。

Output Format

输出一个整数，即答案对 $998\,244\,353$ 取模后的结果。

3
1 2 4

332748120

Hint

（由 ChatGPT 4o 翻译）