配点 : $600$ 点

問題文

$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$ で出力してください。

注記

有理数を出力する際は、まずその有理数を分数 $\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$
• 入力はすべて整数

入力

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

$N$

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

出力

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

3
1 2 2

1
665496237
2

$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$ となります。

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

1
725995895
532396991
768345657
786495555
937744700
574746754
48399732
707846002
907494873
7