打铁之人

2000MS 512MB

题目描述

Awerty 是一名参赛者，正在参加一个包含 $n$ 个不同项目的锦标赛。对于每个项目 $i$，Awerty 都有一个“熟练度加成”，用正整数 $a_i$ 表示。他必须按照某种顺序依次参加所有 $n$ 个项目。

Awerty 在某个项目中未能获得奖牌的概率与他的累积经验有关。对于给定的项目顺序 $p = (p_1, p_2, \ldots, p_n)$，过程如下：

1. 对于第一个项目 $p_1$，他失败的概率是 $\frac{1}{a_{p_1}}$。
2. 对于第二个项目 $p_2$，累积熟练度为 $a_{p_1} + a_{p_2}$。（在第一个项目失败的前提下）他失败的概率是 $\frac{1}{a_{p_1} + a_{p_2}}$。
3. 通常情况下，对于第 $k$ 个项目 $p_k$，累积熟练度为 $S_k = \sum_{j=1}^{k} a_{p_j}$。在之前 $k-1$ 个项目都失败的条件下，他在项目 $p_k$ 失败的条件概率是 $\frac{1}{S_k}$。

然而，Awerty 的心态很差，他在最后一个项目时焦虑达到了顶峰。这对他的表现产生了负面影响。对于序列中的最后一个项目$p_n$，失败的条件概率要乘以该项目的熟练度加成 $a_{p_n}$。因此，（在他之前所有项目都失败的情况下）最后一个项目失败的概率是 $\frac{a_{p_n}}{S_n}$。

Awerty 不知道每个项目的熟练度加成，所以他决定以均匀随机的顺序参加项目。所有 $n!$ 种可能的顺序出现的概率相等。

你的任务是计算 Awerty 在整个锦标赛中未能赢得任何一枚奖牌的总概率。

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。

对于每个测试用例：

• 第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示项目的数量。
• 第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)，表示每个项目的熟练度加成。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出描述

对于每个测试用例，输出一行包含一个整数：模 $P = 998244353$ 后的总概率。具体来说，如果答案是分数 $\frac{A}{B}$，你应该输出 $A \cdot B^{P - 2} \pmod{P}$ 的值。可以证明，答案一定是个分数。

输入样例

2
5
12 16 12 15 19
5
3 9 11 6 6

输出样例

280573384
431099830