题目描述

$N$ 個のキャンディが左右一列に並んでいます。
それぞれのキャンディは、色 $1$、色 $2$、$\ldots$ 、色 $10^9$ の、$10^9$ 種類の色のうちいずれかの色をしています。
$i\ =\ 1,\ 2,\ \ldots,\ N$ について、左から $i$ 番目のキャンディの色は色 $c_i$ です。

高橋君は並んでいる $N$ 個のキャンディのうち $K$ 個を選び、選んだ $K$ 個のキャンディをすべてもらいます。
ここで、$N$ 個のキャンディから $K$ 個を選ぶ組み合わせの個数は二項係数を用いて $\binom{N}{K}$ 個と表せますが、 高橋君は $\binom{N}{K}$ 通りの選び方のうちいずれか一つを等確率でランダムに選びます。

高橋君はいろいろな色のキャンディを食べたいので、もらうキャンディに含まれる色の種類数が多いほどうれしい気持ちになります。
$K\ =\ 1,\ 2,\ \ldots,\ N$ のそれぞれの場合について、高橋君がもらうキャンディに含まれる色の種類数の期待値を求めてください。
ここで、求める答えは有理数となることが証明できます。答えとなる有理数を注記で述べるように $\bmod\ 998244353$ で出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$N$ 行出力せよ。$i$ 行目には $K\ =\ i$ の場合における高橋君がもらうキャンディに含まれる色の種類数の期待値を、注記に述べるように $\bmod\ 998244353$で出力せよ。

题目大意

现在有 $n$ 个糖果, 每个糖果有一种颜色 $c_i$.

现在高桥君想要在中间选 $k$ 个糖果. 由于他想吃最多种颜色的糖果, 所以他的快乐值是选择的糖果的颜色种类数.

例如, 选择糖果的颜色是 $\{2,3,3\}$, 那么他的快乐值是 $2$.

对于 $\forall k \in [1,n]$, 求出高桥君随机选择 $k$ 个糖果的快乐值的期望值, 对 $998244353$ 取模.

$n \le 5 \times 10^4$, $c_i \le 10^9$.

3
1 2 2

1
665496237
2

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

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7

提示

注記

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。ここで、$x,\ y$ は整数であり、$x$ は $998244353$ で割り切れてはなりません（この問題の制約下で、そのような表現は必ず可能です）。そして、$xz\ \equiv\ y\ \pmod{998244353}$ を満たすような $0$ 以上 $998244352$ 以下の唯一の整数 $z$ を出力してください。

制約

• $1\ \leq\ N\ \leq\ 5\ \times\ 10^4$
• $1\ \leq\ c_i\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

$K\ =\ 1$ のとき、高橋君がもらうキャンディの組み合わせは、「 $1$ 番目のみ」「 $2$ 番目のみ」「 $3$ 番目のみ」の $3$ 通りがあります。 いずれの場合も、含まれる色は $1$ 種類です。よって、含まれる色の種類数の期待値は $1$ となります。 $K\ =\ 2$ のとき、高橋君がもらうキャンディの組み合わせは、「 $1$ 番目と $2$ 番目」「 $2$ 番目と $3$ 番目」「 $1$ 番目と $3$ 番目」の $3$ 通りがあります。 - 「 $1$ 番目と $2$ 番目」をもらう場合、含まれる色は $2$ 種類 - 「 $2$ 番目と $3$ 番目」をもらう場合、含まれる色は $1$ 種類 - 「 $1$ 番目と $3$ 番目」をもらう場合、含まれる色は $2$ 種類 となりますから、含まれる色の種類数の期待値は、$ \frac{1}{3}\ \cdot\ 2\ +\ \frac{1}{3}\ \cdot\ 1\ +\ \frac{1}{3}\ \cdot\ 2\ =\ \frac{5}{3} $ です。 注記に述べたように、$\bmod\ 998244353$ で出力することに注意してください。 $K\ =\ 3$ のとき、高橋君がもらうキャンディの組み合わせは、「 $1,\ 2,\ 3$ 番目のすべて」の $1$ 通りのみであり、含まれる色は $2$ 種類です。 よって、含まれる色の種類数の期待値は $2$ となります。