Betrachte $n$ Ausgangszeichenketten aus Kleinbuchstaben, wobei keine Ausgangszeichenkette ein Präfix einer anderen ist. Nun werden $k$ dieser Zeichenketten ausgewählt (keine mehr als einmal) und aneinandergehängt. Auf diese Weise lassen sich so viele zusammengesetzte Zeichenketten bilden:

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

Alle durch dieses Verfahren erzeugbaren zusammengesetzten Zeichenketten werden alphabetisch sortiert. Gegeben ist eine zusammengesetzte Testzeichenkette, die garantiert in dieser Liste vorkommt. Bestimme ihre Position in der alphabetisch sortierten Liste aller zusammengesetzten Zeichenketten, modulo $10^9+7$. Die erste zusammengesetzte Zeichenkette der Liste hat Position $1$.

Eingabe

Jede Eingabe besteht aus einem einzelnen Testfall. Beachte, dass dein Programm möglicherweise mehrfach mit verschiedenen Eingaben ausgeführt wird. Jeder Testfall beginnt mit einer Zeile mit zwei ganzen Zahlen, zuerst $n$ und dann $k$ ($1\le k\le n$). Dabei ist $n$ die Anzahl der Ausgangszeichenketten und $k$ die Anzahl der Ausgangszeichenketten, die zum Bilden zusammengesetzter Zeichenketten ausgewählt werden. Die Obergrenzen für $n$ und $k$ ergeben sich aus den in den folgenden Absätzen angegebenen Beschränkungen für die Zeichenketten.

Jede der nächsten $n$ Zeilen enthält eine Zeichenkette aus einem oder mehreren Kleinbuchstaben a bis z. Dies sind die $n$ Ausgangszeichenketten. Es ist garantiert, dass keine Ausgangszeichenkette ein Präfix einer anderen Ausgangszeichenkette ist.

Die letzte Zeile enthält schließlich eine weitere Zeichenkette, die nur aus Kleinbuchstaben a bis z besteht. Dies ist die zusammengesetzte Testzeichenkette, deren Position in der sortierten Liste du bestimmen sollst. Es ist garantiert, dass sie durch Aneinanderhängen von $k$ verschiedenen Ausgangszeichenketten entsteht.

Die Summe der Längen aller Eingabezeichenketten einschließlich der Testzeichenkette überschreitet $10^6$ Buchstaben nicht.

Ausgabe

Gib eine einzelne ganze Zahl aus: die Position der zusammengesetzten Testzeichenkette in der Liste der sortierten zusammengesetzten Zeichenketten. Gib diese Zahl modulo $10^9+7$ aus.

Beispiele

Eingabe 1

5 3
a
b
c
d
e
cad

Ausgabe 1

26

Eingabe 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

Ausgabe 2

12451