问题陈述

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

将这 $N$ 名学生按照他们的名字的字典顺序分配学生 ID $1, 2, 3, \ldots, N$。然而，与普通的小写英文字母顺序不同，其中 a 是最小的，z 是最大的。我们使用以下顺序：

• 首先，高桥校长从长度为 $26$ 的字符串 abcdefghijklmnopqrstuvwxyz 的 $26!$ 种排列中均匀随机选择一个字符串 $P$。
• 在 $P$ 中出现在前面的小写英文字母被认为更小。

对于每个学生，找到分配的学生 ID 的期望值，取模 $998244353$（参见注释）。

什么是字典顺序？

如果字符串 $S = S_1S_2\ldots S_{|S|}$ 按照字典顺序小于字符串 $T = T_1T_2\ldots T_{|T|}$，则称字符串 $S$ 比字符串 $T$ 字典顺序小，如果满足以下 1. 和 2. 中的一个。这里，$|S|$ 和 $|T|$ 分别表示 $S$ 和 $T$ 的长度。

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

注释

我们可以证明所寻求的期望值总是一个有理数。而且，在此问题的约束条件下，当该值由两个互质的整数 $P$ 和 $Q$ 表示为 $\\frac{P}{Q}$ 时，我们可以证明存在一个唯一的整数 $R$，满足 $R \\times Q \\equiv P\\pmod{998244353}$ 和 $0 \leq R < 998244353$。找到这样的 $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$ 的学生 ID 的期望值，取模 $998244353$。

示例输入 1

3
a
aa
ab

示例输出 1

1
499122179
499122179

分配给学生 $1$ 的学生 ID 的期望值是 $1$；分配给学生 $2$ 和 $3$ 的学生 ID 的期望值是 $\\frac{5}{2}$。

注意，答案应该以取模 $998244353$ 打印。例如，学生 $2$ 和 $3$ 的所寻求的期望值是 $\\frac{5}{2}$，我们有 $2 \times 499122179 \equiv 5\pmod{998244353}$，因此应该打印 $499122179$。

示例输入 2

3
a
aa
aaa

示例输出 2

1
2
3