Description

Lily White 在玩字符串。作为一个妖精，她不擅长复杂的语言。因此，她喜欢只包含一种字母的字符串，她称这种长度为 $x$ 的字符串为“$x$-CON 字符串”。例如，qqqq 是一个“$4$-CON 字符串”，而 aaab 不是任何类型的“CON 字符串”。

Lily White 组成了一个数组 $a$。它包含 $n$ 个长度为 $m$ 的字符串，她将用来迎接春天。对于 $1,2,\ldots, n$ 的每一个排列，我们将当前排列记为 $p=\{p_1,p_2,\cdots,p_n\}$。Lily White 按照 $a_{p_1},a_{p_2},\cdots,a_{p_n}$ 的顺序将数组 $a$ 中的所有字符串连接成一个长度为 $nm$ 的字符串 $s$。

由于她喜欢 $k$-CON 字符串，她想知道由所有 $n!$ 个排列组成的 $s$ 的所有非空子串中“$k$-CON 字符串”的数量之和。由于答案可能非常大，只需输出答案对 $998,244,353$（一个大质数）取模的结果。

Input Format

第一行包含三个整数 $n,m,k$。

接下来有 $n$ 行，每行包含一个长度为 $m$ 的字符串。第 $(i+1)$ 行的字符串表示 $a_i$。

Output Format

输出一个整数，即答案对 $998,244,353$ 取模的结果。

3 3 5
aaa
baa
baa

4

3 3 2
xyz
qaq
aba

0

5 3 2
cca
cbb
acb
bbb
acb

600

5 3 5
aba
bbb
bbb
aba
bcb

120

Hint

解释

示例 #1

• 对于排列 $1,2,3$，形成的 $s$ 是 aaabaabaa，在这个字符串的非空子串中没有“$5$-CON 字符串”。
• 对于排列 $1,3,2$，形成的 $s$ 是 aaabaabaa，在这个字符串的非空子串中没有“$5$-CON 字符串”。
• 对于排列 $2,1,3$，形成的 $s$ 是 baaaaabaa，这个字符串有一个子串 aaaaa 是“$5$-CON 字符串”。
• 对于排列 $2,3,1$，形成的 $s$ 是 baabaaaaa，这个字符串有一个子串 aaaaa 是“$5$-CON 字符串”。
• 对于排列 $3,1,2$，形成的 $s$ 是 baaaaabaa，这个字符串有一个子串 aaaaa 是“$5$-CON 字符串”。
• 对于排列 $3,2,1$，形成的 $s$ 是 baabaaaaa，这个字符串有一个子串 aaaaa 是“$5$-CON 字符串”。

综上所述，答案是 $0+0+1+1+1+1=4$。

示例 #2

在长度为 $3$ 的所有全排列中，将有六个不同的 $s$：xyzqaqaba，xyzabaqaq，qaqxyzaba，qaqabaxyz，abaqaqxyz 和 abaxyzqaq。这些字符串中没有任何非空子串是“$2$-CON 字符串”。所以答案是 $0$。

约束

$2\le k \le n\cdot m\le 10^6; 1\le m \le 100$。$a_i$ 仅包含小写英文字母。

题面翻译由 ChatGPT-4o 提供。