Considere $n$ cadeias iniciais de letras minúsculas, em que nenhuma cadeia inicial é prefixo de outra cadeia inicial. Agora, considere escolher $k$ dessas cadeias (sem escolher nenhuma mais de uma vez) e concatená-las. É possível formar a seguinte quantidade de cadeias compostas:
$$n \times (n-1) \times (n-2) \times \cdots \times (n-k+1)$$
Considere ordenar alfabeticamente todas as cadeias compostas que podem ser obtidas por esse processo. É dada uma cadeia composta de teste, que garantidamente pertence a essa lista. Determine a posição dessa cadeia de teste na lista de todas as cadeias compostas em ordem alfabética, módulo $10^9+7$. A primeira cadeia composta da lista está na posição $1$.
Entrada
Cada entrada consiste num único caso de teste. Observe que o programa pode ser executado várias vezes com entradas diferentes. Cada caso começa com uma linha com dois inteiros, primeiro $n$ e depois $k$ ($1 \le k \le n$), em que $n$ é o número de cadeias iniciais e $k$ é o número de cadeias iniciais escolhidas para formar cadeias compostas. Os limites superiores de $n$ e $k$ são determinados pelas restrições sobre as cadeias nos parágrafos seguintes.
Cada uma das próximas $n$ linhas contém uma cadeia com uma ou mais letras minúsculas de a a z. Essas são as $n$ cadeias iniciais. É garantido que nenhuma cadeia inicial é prefixo de outra cadeia inicial.
Por fim, a última linha contém outra cadeia, formada apenas por letras minúsculas de a a z. Essa é a cadeia composta de teste, cuja posição na lista ordenada deve ser determinada. É garantido que ela é uma concatenação de $k$ cadeias iniciais distintas.
A soma dos comprimentos de todas as cadeias da entrada, incluindo a cadeia de teste, não excede $10^6$ letras.
Saída
Apresente um único inteiro: a posição em que a cadeia composta de teste aparece na lista ordenada de cadeias compostas. Apresente esse número módulo $10^9+7$.
Exemplos
Entrada 1
5 3 a b c d e cad
Saída 1
26
Entrada 2
8 8 font lewin darko deon vanb johnb chuckr tgr deonjohnbdarkotgrvanbchuckrfontlewin
Saída 2
12451