Problem Description

Biologists are studying $n$ species.

For the $i$-th species, its DNA sequence is $s[i]$. The $j$-th base is $s[i][j]$, and every base must be one of A, G, C, T.

The biologists want to find some common features among a subset of these species. They are now focusing on contiguous base sequences of length $k$ that appear in at least $m$ species. More precisely, the sequences that the scientists care about are represented by a $2m$-tuple $(i_1,p_1,i_2,p_2 \cdots ,i_m,p_m)$, which satisfies:

$$1 \le i_1<i_2< \cdots <i_m \le n$$

and for all $q(0 \le q<k)$,

$$s[i_1][p_1+q]=s[i_2][p_2+q]= \cdots =s[i_m][p_m+q]$$

Now, given the DNA sequences of all species, tell the scientists how many such $2m$-tuples need to be considered. If two $2m$-tuples differ at any position, they are considered different tuples.

Input Format

The first line contains three integers $n$, $m$, $k$, separated by one space, with meanings as described above.

The next $n$ lines each contain a string representing the DNA sequence of one species.

The DNA sequences are numbered from $1$ to $n$. Within each sequence, bases are numbered starting from $1$ in order. The DNA sequence lengths of different species may be different.

Output Format

Output one integer, the number of tuples to be considered.

The answer may be very large. You need to output the remainder of the answer modulo $1000000007(10^9+7)$.

3 2 2
ATC
TCG
ACG

2

4 3 3
AAA
AAAA
AAA
AAA

7

Hint

Constraints

For $20\%$ of the testdata, $k \le 5,$ and the total length $L$ of all strings satisfies $L \le 100$.

For $30\%$ of the testdata, $L \le 10000$.

For $60\%$ of the testdata, $L \le 30000$.

For $100\%$ of the testdata, $n \le 5,m \le 5,1 \le k \le L \le 10^5$.

It is guaranteed that all DNA sequences are non-empty and contain only the four letters A, G, C, T.

Time limit: 1 second, 256 MB. Lanqiao Cup 2016, 7th National Final.

Translated by ChatGPT 5