彩色糖果 2

题目描述

有 $N$ 颗糖果从左到右排成一列。

每颗糖果具有以下 $10^9$ 种颜色之一：颜色 $1$、颜色 $2$、$\ldots$、颜色 $10^9$。

对每个 $i = 1, 2, \ldots, N$，从左数第 $i$ 颗糖果的颜色为 $c_i$。

高桥君将从 $N$ 颗糖果中选出 $K$ 颗并得到这 $K$ 颗糖果。

从 $N$ 颗中选出 $K$ 颗的方式有 $\binom{N}{K}$ 种，其中 $\binom{N}{K}$ 是二项式系数。高桥君将等概率地随机选择这 $\binom{N}{K}$ 种方式中的一种。

因为高桥君想吃五颜六色的糖果，他得到的糖果颜色种类越多越开心。

对每个 $K = 1, 2, \ldots, N$，求出高桥君得到的糖果中不同颜色数量的期望值。

可以证明所求值为有理数。请按「提示」中的说明，输出这个有理数对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入给出：

$N$
$c_1$ $c_2$ $\ldots$ $c_N$

输出格式

输出 $N$ 行。第 $i$ 行输出在 $K = i$ 的情形下，高桥君得到的糖果中不同颜色数量的期望值对 $998244353$ 取模的结果，具体见「提示」中的说明。

样例

3
1 2 2

1
665496237
2

当 $K = 1$ 时，他得到第 1 颗、第 2 颗或第 3 颗糖果。无论哪种情况，他的糖果都只有一种颜色，所以不同颜色数量的期望值为 $1$。

当 $K = 2$ 时，他得到第 1、2 颗，第 2、3 颗，或第 1、3 颗糖果。

如果他得到第 1、2 颗，它们有两种不同的颜色。

如果他得到第 2、3 颗，它们有一种颜色。

如果他得到第 1、3 颗，它们有两种不同的颜色。

因此，不同颜色数量的期望值为 $\frac{1}{3} \cdot 2 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 2 = \frac{5}{3}$。

注意要按「提示」中的说明对 $998244353$ 取模。

当 $K = 3$ 时，他总是得到第 1、2、3 颗糖果，它们有两种不同的颜色，所以不同颜色数量的期望值为 $2$。

11
3 1 4 1 5 9 2 6 5 3 5

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

数据范围

• $1 \le N \le 5 \times 10^4$
• $1 \le c_i \le 10^9$
• 输入中的所有值均为整数。

提示

当你输出有理数时，先把它写成 $\frac{y}{x}$ 的形式，其中 $x, y$ 是整数且 $x$ 不被 $998244353$ 整除（在本问题的约束下，这样的表示总是存在）。然后，你需要输出满足 $xz \equiv y \pmod{998244353}$ 且介于 $0$ 和 $P - 1$（含两端）之间的唯一整数 $z$，这里 $P = 998244353$。