随机学生编号

题目描述

高桥小学有 $N$ 名新生。对于 $i = 1, 2, \ldots, N$，第 $i$ 名新生的名字为 $S_i$（由小写英文字母组成的字符串）。$N$ 名新生的名字互不相同。

这 $N$ 名学生将按照名字的字典序从小到大获得学生编号 $1, 2, 3, \ldots, N$。但是，不使用通常的 a 最小、z 最大的小写英文字母顺序，而是使用以下顺序：

首先，校长高桥从长度为 $26$ 的字符串 abcdefghijklmnopqrstuvwxyz 的 $26!$ 个排列中等概率随机选择字符串 $P$。

在 $P$ 中出现位置越靠前的小写英文字母被认为越小。

对于每名学生，求出其学生编号的期望值（对 $998244353$ 取模，见 Notes）。

什么是字典序？ 设 $|S|$ 和 $|T|$ 分别表示字符串 $S = S_1S_2\ldots S_{|S|}$ 和 $T = T_1T_2\ldots T_{|T|}$ 的长度。当满足以下 1、2 中的任意一条时，称 $S$ 按字典序小于 $T$：

1. $|S| \lt |T|$ 且 $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$。
2. 存在整数 $1 \le i \le \min\lbrace |S|, |T| \rbrace$ 满足以下两个条件：
   • $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$
   • $S_i$ 是比 $T_i$ 更小的字符。

Notes

可以证明所求期望值总是有理数。此外，在本问题的约束下，当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时，可以证明存在唯一的整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \le R \lt 998244353$。求这样的 $R$。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出 $N$ 行。 对于每个 $i = 1, 2, \ldots, N$，第 $i$ 行输出学生 $i$ 的学生编号期望值（对 $998244353$ 取模）。

样例

3
a
aa
ab

1
499122179
499122179

学生 $1$ 的学生编号期望值为 $1$；学生 $2$ 和学生 $3$ 的学生编号期望值均为 $\frac{5}{2}$。

注意答案应对 $998244353$ 取模输出。 例如，学生 $2$ 和 $3$ 的期望值为 $\frac{5}{2}$， 且 $2 \times 499122179 \equiv 5\pmod{998244353}$， 因此应输出 $499122179$。

3
a
aa
aaa

1
2
3

数据范围

• $2 \le N$
• $N$ 是整数。
• $S_i$ 是由小写英文字母组成的长度至少为 $1$ 的字符串。
• 给定字符串的长度之和至多为 $5 \times 10^5$。
• 当 $i \neq j$ 时，$S_i \neq S_j$。