Rozważmy $n$ początkowych napisów złożonych z małych liter, przy czym żaden początkowy napis nie jest prefiksem innego początkowego napisu. Teraz wybierzmy $k$ spośród tych napisów (żadnego więcej niż raz) i połączmy je ze sobą. W ten sposób można utworzyć następującą liczbę napisów złożonych:

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

Rozważmy posortowanie w porządku alfabetycznym wszystkich napisów złożonych, które można otrzymać w ten sposób. Dany jest testowy napis złożony, który na pewno znajduje się na tej liście. Znajdź pozycję tego testowego napisu złożonego na alfabetycznie uporządkowanej liście wszystkich napisów złożonych, modulo $10^9+7$. Pierwszy napis złożony na liście znajduje się na pozycji $1$.

Wejście

Każde wejście zawiera jeden przypadek testowy. Zwróć uwagę, że twój program może być uruchamiany wielokrotnie dla różnych danych wejściowych. Każdy przypadek testowy zaczyna się od wiersza z dwiema liczbami całkowitymi: najpierw $n$, a potem $k$ ($1 \le k \le n$), gdzie $n$ jest liczbą początkowych napisów, a $k$ jest liczbą początkowych napisów wybieranych do utworzenia napisów złożonych. Górne ograniczenia na $n$ i $k$ wynikają z ograniczeń dotyczących napisów, podanych w kolejnych akapitach.

Każdy z następnych $n$ wierszy zawiera napis składający się z co najmniej jednej małej litery od a do z. Są to początkowe napisy. Gwarantuje się, że żaden z początkowych napisów nie jest prefiksem innego początkowego napisu.

Na końcu, ostatni wiersz zawiera jeszcze jeden napis, złożony wyłącznie z małych liter od a do z. Jest to testowy napis złożony, którego pozycję na posortowanej liście należy znaleźć. Gwarantuje się, że ten testowy napis złożony jest połączeniem $k$ różnych początkowych napisów.

Suma długości wszystkich napisów wejściowych, wliczając napis testowy, nie przekroczy $10^6$ liter.

Wyjście

Wypisz jedną liczbę całkowitą: pozycję testowego napisu złożonego na liście posortowanych napisów złożonych. Wypisz tę liczbę modulo $10^9+7$.

Przykład

Wejście 1

5 3
a
b
c
d
e
cad

Wyjście 1

26

Wejście 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

Wyjście 2

12451