Description

在简单版本中，保证数组 $\mathbf a$ 中的任何字符串至少包含两个不同的字母。

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 4
aab
baa
baa

4

3 3 2
xyz
qaq
aba

0

Hint

解释

示例 #1

• 对于排列 $1,2,3$，形成的 $s$ 是 aabbaabaa，这个字符串中的非空子串没有一个是“$4$-CON 字符串”。
• 对于排列 $1,3,2$，形成的 $s$ 是 aabbaabaa，这个字符串中的非空子串没有一个是“$4$-CON 字符串”。
• 对于排列 $2,1,3$，形成的 $s$ 是 baaaabbaa，这个字符串有一个子串 aaaa 是“$4$-CON 字符串”。
• 对于排列 $2,3,1$，形成的 $s$ 是 baabaaaab，这个字符串有一个子串 aaaa 是“$4$-CON 字符串”。
• 对于排列 $3,1,2$，形成的 $s$ 是 baaaabbaa，这个字符串有一个子串 aaaa 是“$4$-CON 字符串”。
• 对于排列 $3,2,1$，形成的 $s$ 是 baabaaaab，这个字符串有一个子串 aaaa 是“$4$-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$ 仅包含小写英文字母。

在简单版本中，我们确保数组 $\mathbf a$ 中的任何字符串至少包含两个不同的字母。

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