P7943 「Wdcfr-1」CONsecutive and CONcat (hard version)

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$（一个大质数）取模的结果。

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

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

### 解释 #### 示例 \#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 提供。