T68477 [II] 珍珠游戏

LZC喜欢玩游戏。 新年刚过，他用他的压岁钱买了一串珍珠，并把他们串起来，做成珍珠项链。特别的，这个项链并没有首尾连接，也就是说，它真的是一条“链”。 这条珍珠项链长度为$N$，贪玩的LZC又突然想把这条项链拆开来。 已知每颗珍珠的价值为$w_i$，LZC每次会在当前未被拆下的珍珠中，随意选择一颗珍珠，然后得到其所在链的珍珠价值和的收益，然后把这颗珍珠拆下，将其所在的链延此分裂成两条链（链可以是空的）。当所有珍珠都被拆下时停止。 LZC想知道在所有操作方法下，他能够得到收益和的期望，你能帮他解决这个问题吗？ 答案对 $998244353$ 取模。

第一行，一个正整数 $N$。 第二行，$N$ 个正整数描述$w_i$。

输出期望的价值和对 $998244353$ 取模的结果。

|数据百分比|限制| |-|-| |$10\%$|$N \le 10$| |$20\%$|$N \le 20$| |$30\%$|$N \le 500$| |$50\%$|$N \le 3000$| |$100\%$|$N \le 2 \cdot 10^6,a_i \le 10^9$|