問題文

高橋小学校には $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$ より小さい文字である。

注記

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

入力例 1

3
a
aa
ab

出力例 1

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$ を出力します。

入力例 2

3
a
aa
aaa

出力例 2

1
2
3