[AdditionalFile6847.zip](file://AdditionalFile6847.zip?type=additional_file)

#6847. zhylj 的抽卡

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

有 $n$ 个物品，编号为 $1$ 到 $n$。从第一个时刻开始的每个时刻都会恰好出现一个物品，物品 $i$ 会以 $p_i$ 的概率出现，小 z 将统计所有物品的第一次出现时间，直到所有物品均出现了至少一次。

记物品 $i$ 的第一次出现时间为 $t_i$，那么定义出现时间的平均数 $\overline t$ 和方差 $\sigma^2$ 为：

$$\overline t = \frac 1n\sum_{i=1}^n t_i$$ $$\sigma^2 = \frac 1n\sum_{i=1}^n (t_i - \overline t)^2$$

小 z 想要求得 $\overline t,\sigma^2$ 的期望，但是因为小 z 不会，所以只能来求助你。

你只需要告诉小 z 答案对 $998244353$ 取模后的答案。

输入格式

输入包含两行。

第一行包含一个整数 $n$，表示物品的个数。

第二行包含 $n$ 个整数 $q_1,q_2,\cdots,q_n$，表示编号为 $i$ 的物品在每个时刻出现的概率为 $p_i=\dfrac {q_i}{\sum_{j=1}^n q_j}$。

输出格式

输出包含两行。

第一行包含一个整数，表示 $\overline t$ 的期望。

第二行包含一个整数，表示 $\sigma^2$ 的期望。

以上两行均为对 $998244353$ 取模后的结果，更具体地，可以证明答案能被表示为既约的分数 $\dfrac ab$，存在唯一的整数 $x\in[0,998244353)$ 使得 $xb\equiv a\pmod {998244353}$，你需要输出这个 $x$。

样例 1

输入

3
1 2 2

输出

332748121
739440270

可以证明，对于第一问，答案为 $\dfrac {10}3$，对于第二问，答案为 $\dfrac {230}{27}$。

样例 2

输入

6
1 1 4 5 1 4

输出

266198504
655637177

数据范围与提示

对于所有的测试数据，$2\le n\le 10^5$，$1\le q_i \le 10^8$，$\sum q_i \not \equiv 0\pmod{ 998244353}$。

本题共 $20$ 个测试点，对于第 $i$ 个测试点，$n = i\cdot 5000$。