配点 : $600$ 点

問題文

高橋小学校には $N$ 人の新入生がおり、$i = 1, 2, \ldots, N$ について $i$ 番目の新入生の名前は $S_i$ （英小文字のみからなる文字列）です。 $N$ 人の名前は相異なります。

$N$ 人の新入生には、名前が辞書順で小さい者から順に $1, 2, 3, \ldots, N$ と学籍番号が付与されます。 ただしその際には、a が最小で z が最大である通常の英小文字の順序の代わりに、下記で定まる順序を用います。

• まず高橋校長が、長さ $26$ の文字列 abcdefghijklmnopqrstuvwxyz を並べ替えて得られる $26!$ 個の文字列の中から $1$ つを、等確率でランダムに文字列 $P$ として選ぶ。
• $P$ で前にある英小文字ほど小さい英小文字とみなす。

$N$ 人の新入生それぞれについて、与えられる学籍番号の期待値を $\mathrm{mod}\, 998244353$ で出力してください（注記参照）。

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、$R \times Q \equiv P\pmod{998244353}$ かつ $0 \leq R \lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $2 \leq N$
• $N$ は整数
• $S_i$ は英小文字のみからなる長さ $1$ 以上の文字列
• 与えられる文字列の長さの総和は $5 \times 10^5$ 以下
• $i \neq j \Rightarrow S_i \neq S_j$

入力

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

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

出力

$N$行出力せよ。 $i = 1, 2, \ldots, N$ について、$i$ 行目には $i$ 番目の新入生に与えられる学籍番号の期待値を $\mathrm{mod}\, 998244353$ で出力せよ。

3
a
aa
ab

1
499122179
499122179

$1$ 番目の新入生に与えられる学籍番号の期待値は $1$ であり、$2, 3$ 番目の新入生に与えられる学籍番号の期待値は $\frac{5}{2}$ です。

答えを $\mathrm{mod}\, 998244353$ で出力することに注意してください。 例えば、$2, 3$ 番目の新入生についての出力では、求める期待値が $\frac{5}{2}$ であり、 $2 \times 499122179 \equiv 5\pmod{998244353}$ が成り立つので、 $499122179$ を出力します。

3
a
aa
aaa

1
2
3