生物學(xué)家正在對(duì)n個(gè)物種進(jìn)行研究。
其中第i個(gè)物種的DNA序列為s[i]，其中的第j個(gè)堿基為s[i][j],堿基一定是A、T、G、C之一。
生物學(xué)家想找到這些生物中一部分生物的一些共性，他們現(xiàn)在關(guān)注那些至少在m個(gè)生物中出現(xiàn)的長(zhǎng)度為k的連續(xù)堿基序列。準(zhǔn)確的說(shuō)，科學(xué)家關(guān)心的序列用2m元組(i1,p1,i2,p2....im,pm)表示，
滿足:
1<=i1<i2<....<im<=n;
且對(duì)于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=....=s[im][pm+q]。

現(xiàn)在給定所有生物的DNA序列，請(qǐng)告訴科學(xué)家有多少的2m元組是需要關(guān)注的。如果兩個(gè)2m元組有任何一個(gè)位置不同，則認(rèn)為是不同的元組。

輸入的第一行包含三個(gè)整數(shù)n、m、k，兩個(gè)整數(shù)之間用一個(gè)空格分隔，意義如題目所述。
接下來(lái)n行，每行一個(gè)字符串表示一種生物的DNA序列。
DNA序列從1至n編號(hào)，每個(gè)序列中的堿基從1開(kāi)始依次編號(hào)，不同的生物的DNA序列長(zhǎng)度可能不同。

輸出一個(gè)整數(shù)，表示關(guān)注的元組個(gè)數(shù)。
答案可能很大，你需要輸出答案除以1000000007的余數(shù)。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯