强迫症

题目背景

小 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. 两条边在端点处**不视作相交**。 1. **没有边的图(即只有 $n$ 个点,之间没有边相连)也合法** 1. 点**按顺时针从 $1$ 到 $n$** 编号。 1. 图中**不能有自环和重边**

输入输出格式

输入格式


第一行一个正整数 $n$,意义如上。 接下来一行 $n$ 个非负整数,第 $i$ 个数为 $a_i$,表示第 $i$ 个点的点权。

输出格式


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

输入输出样例

输入样例 #1

4
1 1 1 1

输出样例 #1

665496238

输入样例 #2

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

输出样例 #2

748867567

说明

对于样例一,全部 $64$ 张图如下: ![](https://cdn.luogu.com.cn/upload/image_hosting/zfa8hs0v.png) 其中左侧 $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$。 ------------ 如果你不知道如何对一个有理数取模,请自行百度「乘法逆元」