P8643 [Lanqiao Cup 2016 National AC] Bases

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

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 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)$.

### 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