P6694 强迫症
题目背景
小 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. 图中**不能有自环和重边**
输入格式
无
输出格式
无
说明/提示
对于样例一，全部 $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$。
------------
如果你不知道如何对一个有理数取模，请自行百度「乘法逆元」