Colorful Candies 2

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有 $N$ 个糖果，第 $i$ 个糖果的颜色为 $c_i$。对每个 $K=1,2,\ldots,N$，从全部 $\binom NK$ 个大小为 $K$ 的糖果集合中等概率随机选择一个，求所选糖果中不同颜色数量的期望值。

答案是有理数。若答案可表示为 $y/x$ 且 $x$ 不被 $998244353$ 整除，请输出唯一的 $z\in[0,998244352]$，满足 $xz\equiv y\pmod{998244353}$。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $c_1,c_2,\ldots,c_N$。

输出格式

输出 $N$ 行，第 $K$ 行表示选择 $K$ 个糖果时的答案。

样例输入 1

3
1 2 2

样例输出 1

1
665496237
2

样例输入 2

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

样例输出 2

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

数据范围

对于全部数据，$1\le N\le5\times10^4$，$1\le c_i\le10^9$。