题目描述

生物学家正在对 $n$ 个物种进行研究。

其中第 $i$ 个物种的 DNA 序列为 $s_i$ ，其中的第 $j$ 个碱基为 $s_{i,j}$ ,碱基一定是 A、T、G、C 之一。

生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在 $m$ 个生物中出现的长度为 $k$ 的连续碱基序列。准确的说，科学家关心的序列用 $2m$ 元组 $( i_1,p_1,i_2,p_2⋯i_m,p_m)$ 表示，满足:

$1≤i_1<i_2<⋯<i_m≤n$ , 且对于所有 $q (0≤q<k)，s_{i1,p_{1+q}}=s_{i2,p_{2+q}}=⋯=s_{im,p_{m+q}}$。

现在给定所有生物的 DNA 序列，请告诉科学家有多少的 $2m$ 元组是需要关注的。如果两个 $2m$ 元组有任何一个位置不同，则认为是不同的元组。

输入描述

输入的第一行包含三个整数 $n、m、k$ ，两个整数之间用一个空格分隔，意义如题目所述。

接下来 $n$ 行，每行一个字符串表示一种生物的 DNA 序列。

DNA 序列从 1 至 $n$ 编号，每个序列中的碱基从 1 开始依次编号，不同的生物的 DNA 序列长度可能不同。

其中， $n≤5,m≤5,1≤k≤L≤10^5$ 。

保证所有 DNA 序列不为空且只会包含 'A' 'G' 'C' 'T' 四种字母。

输出一个整数，表示关注的元组个数。

答案可能很大，你需要输出答案除以 $10^9+7$ 的余数。

3 2 2
ATC
TCG
ACG