题目背景

小 L 是一个严重的强迫症患者。

由于他严重的强迫症，所以他画图时总是要把点画在一个圆上。

题目描述

一天，他问了小 H 和小 W 这样一个问题：

如果在一个圆上有 $n$ 个不同的点，依次标号为 $1$ 到 $n$，有多少种方案能把它们连成一棵树？

小 H & 小 W：这不是sb题吗？

小 L：那如果连边不能相交呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果把「树」换成「图」呢呢？

小 H & 小 W：这不是sb题吗？

小 L：那如果给每个点一个权值 $a_i$，连接 $(i,j)$ 的边权值为 $a_i\times a_j$，求满足上面的图的期望所有边权值之和呢？

小 H & 小 W：这不是sb题吗？

小 L 见自己辛苦做了许久都没写出的题目被 dalao 轻松秒杀后十分郁闷。为了安慰他，你需要帮他做出这个问题。

注意：

1. 两条边在端点处不视作相交。
2. 没有边的图（即只有 $n$ 个点，之间没有边相连）也合法
3. 点按顺时针从 $1$ 到 $n$ 编号。
4. 图中不能有自环和重边

输入格式

第一行一个正整数 $n$，意义如上。

接下来一行 $n$ 个非负整数，第 $i$ 个数为 $a_i$，表示第 $i$ 个点的点权。

输出格式

一个正整数，表示结果。答案对 $998244353$ 取模。

4
1 1 1 1

665496238

13
1 1 4 5 1 4 1 9 1 9 8 1 0

748867567

提示

对于样例一，全部 $64$ 张图如下：

其中左侧 $48$ 张图合法，右侧 $16$ 张图不合法，所有边的权值均为 $1$。

期望边权和为 $\dfrac{8}{3}$，模 $998244353$ 意义下结果为 $665496238$。

数据范围

本题采用捆绑测试。

• Subtask 1( $10\%$ )：$n\leq 6$。
• Subtask 2( $30\%$ )：$n\leq 3000$。
• Subtask 3( $60\%$ )：无特殊限制。

对于 $100\%$ 的数据，$2\leq n\leq 10^5,0\leq a_i\leq10^6$。

Subtask 1 和 Subtask 2 时限 $1s$，Subtask 3 时限 $2s$。

---

如果你不知道如何对一个有理数取模，请自行百度「乘法逆元」