You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

$Diana$ 希望小 $z$ 求得 $\bar t$ , $σ^2$的期望，但是因为小 $z$ 不会，所以只能来求助你。

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

输入格式

从文件 $card.in$ 中读入数据。

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数 $q_1,q_2,...,q_n$ ，表示编号为 $i$ 的物品在每个时刻出现的概率为:

输出格式

输出到文件 $card.out$ 中。

第一行一个非负整数，表示 $\bar t$ 的期望对 $998244353$ 取模的结果。

第二行一个非负整数，表示 $σ^2$ 的期望对 $998244353$ 取模的结果。

样例 1 输入：

3
1 2 2

样例 1 输出：

332748121
739440270

解释 1 解释：

可以证明，$\bar t = \frac{10}{3}$ , $σ^2 = \frac{230}{27}$。

样例 2 输入：

6
1 1 4 5 1 4

样例 2 输出：

266198504
655637177

样例 3 ：

见右侧文件的 $card3.in$ 与 $card3.ans$ 。

评分方式：

本题使用自定义校验器（$Special$ $Judge$）来检验你的答案。

• 若你输出的两行均不正确，你将不会得到该测试点的任何分数。

• 若你输出的第一行正确而第二行不正确，你将得到该测试点 $20$ 的分数。

• 若你输出的第二行正确而第一行不正确，你将得到该测试点 $80$ 的分数。

• 若你输出的两行均正确，你将得到该测试点 $100$ 的分数。

需要注意的是，即使你不知道如何求解正确答案，你输出的答案也必须包含两行两个在 $[0,998244353)$ 中的整数，否则将可能导致未知错误。

数据范围

对于所有测试数据，保证 $2≤n≤5000$ ， $1≤q_i<998244353$ ，$∑q_i \not \equiv 0 (mod998244353)$ 。

每个测试点的具体限制见下表：