AT_abc268_g [ABC268G] Random Student ID

题目描述

题目大意

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

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

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

输入格式

第一行一个整数 $n$。

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

输出格式

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

输入输出样例 #1

输入 #1

3
a
aa
ab

输出 #1

1
499122179
499122179

输入输出样例 #2

输入 #2

3
a
aa
aaa

输出 #2

1
2
3

说明/提示

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