Counting k-CON Substrings Over Permutations

Lily White likes strings that contain exactly one kind of letter and calls such a string of length \(x\) a \(x\)-CON string. For example, qqqq is a 4-CON string, while aaab is not a CON string.

She has an array \(a\) containing \(n\) strings each of length \(m\). For each permutation \(p = \{p_1, p_2, \dots, p_n\}\) of \(\{1,2,\dots, n\}\), she concatenates the strings in that order to form a string \(s\) of length \(nm\). She is interested in the number of non‐empty substrings of \(s\) that are exactly \(k\)-CON strings (i.e. substrings of length \(k\) in which every character is the same).

Compute the sum of the numbers of \(k\)-CON substrings, taken over all \(n!\) permutations of the array, and output the answer modulo \(998\,244\,353\).

Details:

• A \(k\)-CON string is defined as a string of exactly length \(k\) consisting of a single repeated letter.
• Substrings are contiguous segments of the string \(s\). Note that substrings may lie completely inside one string or cross the boundary between two or more strings when the array is concatenated.
• When a substring spans more than one original string, it can be formed by taking a suffix from the first string, (possibly) several full strings (each of which must be entirely composed of that letter) in the middle, and a prefix from the last string. If the first string has a longest uniform suffix of length \(S\) and the last string a longest uniform prefix of length \(P\), then a substring spanning these two strings can form a \(k\)-CON string if there exists \(x\) and \(y\) (with \(1 \le x \le S\) and \(1 \le y \le P\)) such that \(x+y = T\). When more than two strings are spanned, note that any completely included middle string must be itself uniform.

Input constraints (implicit): The first line contains three integers \(n, m, k\). Then \(n\) lines follow, each a string of length \(m\). You may assume the strings consist of lowercase letters and that \(n\) is small enough so that the total contributions over \(n!\) permutations can be computed combinatorially.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\). Each of the next \(n\) lines contains a string of length \(m\) consisting of lowercase English letters.

outputFormat

Output a single integer: the sum of the number of \(k\)-CON substrings over all non-empty substrings of \(s\) (for all \(n!\) permutations), taken modulo \(998\,244\,353\).

sample

2 4 4
qqqq
qqqq

10