题目描述

高橋小学校には $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$ で出力してください（注記参照）。

辞書順で小さいとは？文字列 $S\ =\ S_1S_2\ldots\ S_{|S|}$ が文字列 $T\ =\ T_1T_2\ldots\ T_{|T|}$ より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、$|S|,\ |T|$ はそれぞれ $S,\ T$ の長さを表します。

1. $|S|\ \lt\ |T|$ かつ $S_1S_2\ldots\ S_{|S|}\ =\ T_1T_2\ldots\ T_{|S|}$。
2. ある整数 $ 1\ \leq\ i\ \leq\ \min\lbrace\ |S|,\ |T|\ \rbrace $ が存在して、下記の $2$ つがともに成り立つ。

• $S_1S_2\ldots\ S_{i-1}\ =\ T_1T_2\ldots\ T_{i-1}$
• $S_i$ が $T_i$ より小さい文字である。

输入格式

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

$N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

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

题目大意

题目大意

有 $n$ 个学生，第 $i$ 个学生的名字是一个字符串 $S_i$，编号是 $i$。

接下来校长要按照一种绝妙的字典序来对这 $n$ 个学生的名字排序。他随机选取一个 $\tt{a}\sim\tt{z}$ 的排列，定为 $P$。$P$ 中越早出现的字母，他的字典序就越小。

对于每一个学生，求出他的期望排名，对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行每行一个字符串 $S_i$。

输出格式

输出 $n$ 行，第 $i$ 行表示编号为 $i$ 的学生的期望排名。

数据范围

对于所有数据，我们保证 $S_i$ 只由小写字母组成，并且这些学生的名字互不相同。$n\geqslant 2$，字符串总长度不超过 $5\times 10^5$。

3
a
aa
ab

1
499122179
499122179

3
a
aa
aaa

1
2
3

提示

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $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$

Sample Explanation 1

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