{"raw_statement":[{"iden":"statement","content":"生物学家正在对 $n$ 个物种进行研究。\n\n其中第 $i$ 个物种的 DNA 序列为 $s[i]$，其中的第 $j$ 个碱基为 $s[i][j],$ 碱基一定是 `A`,`G`,`C`,`T` 之一。\n\n生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在 $m$ 个生物中出现的长度为 $k$ 的连续碱基序列。准确的说，科学家关心的序列用 $2m$ 元组 $(i_1,p_1,i_2,p_2 \\cdots ,i_m,p_m)$ 表示，\n\n满足：\n\n$$1 \\le i_1<i_2< \\cdots <i_m \\le n$$\n\n且对于所有 $q(0 \\le q<k)$，\n\n$$s[i_1][p_1+q]=s[i_2][p_2+q]= \\cdots =s[i_m][p_m+q]$$\n\n现在给定所有生物的 DNA 序列，请告诉科学家有多少的 $2m$ 元组是需要关注的。如果两个 $2m$ 元组有任何一个位置不同，则认为是不同的元组。"},{"iden":"input","content":"输入的第一行包含三个整数 $n$，$m$，$k$，两个整数之间用一个空格分隔，意义如题目所述。\n\n接下来 $n$ 行，每行一个字符串表示一种生物的 DNA 序列。\n\nDNA 序列从 $1$ 至 $n$ 编号，每个序列中的碱基从 $1$ 开始依次编号，不同的生物的 DNA 序列长度可能不同。"},{"iden":"output","content":"输出一个整数，表示关注的元组个数。\n\n答案可能很大，你需要输出答案除以 $1000000007(10^9+7)$ 的余数。"},{"iden":"note","content":"### 数据规模与约定\n\n对于 $20\\%$ 的数据，$k \\le 5,$ 所有字符串总长 $L$ 满足 $L \\le 100$。\n\n对于 $30\\%$ 的数据，$L \\le 10000$。\n\n对于 $60\\%$ 的数据，$L \\le 30000$。\n\n对于 $100\\%$ 的数据，$n \\le 5,m \\le 5,1 \\le k \\le L \\le 10^5$。\n\n保证所有 DNA 序列不为空且只会包含`A`,`G`,`C`,`T` 四种字母。\n\n时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛"}],"translated_statement":null,"sample_group":[["3 2 2\nATC\nTCG\nACG","2"],["4 3 3\nAAA\nAAAA\nAAA\nAAA","7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}