Considérons $n$ chaînes initiales de lettres minuscules, telles qu'aucune chaîne initiale ne soit un préfixe d'une autre chaîne initiale. Choisissons maintenant $k$ de ces chaînes (sans choisir une même chaîne plusieurs fois), puis concaténons-les. Le nombre de chaînes composées que l'on peut ainsi former est :

$$n\times(n-1)\times(n-2)\times\cdots\times(n-k+1)$$

Considérons le classement par ordre alphabétique de toutes les chaînes composées obtenues par ce procédé. On vous donne une chaîne composée de test, dont la présence dans cette liste est garantie. Trouvez sa position dans la liste triée de toutes les chaînes composées, modulo $10^9+7$. La première chaîne composée de la liste est à la position $1$.

Entrée

Chaque entrée contient un seul cas de test. Votre programme peut être exécuté plusieurs fois sur des entrées différentes. Chaque cas de test commence par une ligne contenant deux entiers, d'abord $n$, puis $k$ ($1\le k\le n$), où $n$ est le nombre de chaînes initiales et $k$ le nombre de chaînes initiales choisies pour former les chaînes composées. Les bornes supérieures de $n$ et de $k$ sont déterminées par les contraintes sur les chaînes données dans les paragraphes suivants.

Chacune des $n$ lignes suivantes contient une chaîne composée d'une ou plusieurs lettres minuscules de a à z. Ce sont les $n$ chaînes initiales. Il est garanti qu'aucune chaîne initiale n'est un préfixe d'une autre chaîne initiale.

Enfin, la dernière ligne contient une autre chaîne, composée uniquement de lettres minuscules de a à z. Il s'agit de la chaîne composée de test dont vous devez trouver la position dans la liste triée. Il est garanti qu'elle est la concaténation de $k$ chaînes initiales distinctes.

La somme des longueurs de toutes les chaînes de l'entrée, y compris la chaîne de test, ne dépasse pas $10^6$ lettres.

Sortie

Affichez un seul entier : la position de la chaîne composée de test dans la liste triée des chaînes composées. Affichez ce nombre modulo $10^9+7$.

Exemples

Entrée 1

5 3
a
b
c
d
e
cad

Sortie 1

26

Entrée 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

Sortie 2

12451