小文字からなる $n$ 個の元の文字列を考えます。どの元の文字列も、他の元の文字列の接頭辞ではありません。ここで、そのうち $k$ 個の文字列を選び（同じ文字列を複数回選ぶことはできません）、連結することを考えます。このようにして作れる合成文字列の個数は次のとおりです。

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

この操作で得られるすべての合成文字列をアルファベット順に並べることを考えます。この一覧に含まれることが保証された、調べる対象の合成文字列が与えられます。すべての合成文字列をアルファベット順に並べた一覧において、この合成文字列が何番目にあるかを求め、$10^9+7$ で割った余りを出力してください。一覧の最初の合成文字列の位置は $1$ です。

入力

各入力は単一のテストケースからなります。プログラムは、異なる入力に対して複数回実行されることがあります。各テストケースの最初の行には、まず整数 $n$、次に整数 $k$（$1\le k\le n$）が与えられます。$n$ は元の文字列の個数であり、$k$ は合成文字列を作るために選ぶ元の文字列の個数です。$n$ と $k$ の上限は、以下の段落に記載されている文字列に関する制約によって制限されます。

続く $n$ 行には、それぞれ a から z までの小文字を1文字以上含む文字列が与えられます。これらが $n$ 個の元の文字列です。どの元の文字列も、他の元の文字列の接頭辞ではないことが保証されます。

最後の行には、a から z までの小文字のみからなる別の文字列が与えられます。これが調べる対象の合成文字列であり、整列された一覧におけるその位置を求めなければなりません。この合成文字列は、互いに異なる $k$ 個の元の文字列を連結したものであることが保証されます。

調べる対象の文字列を含め、入力中のすべての文字列の長さの合計は $10^6$ 文字を超えません。

出力

整列された合成文字列の一覧において、調べる対象の合成文字列が現れる位置を表す整数を1つ出力してください。この値を $10^9+7$ で割った余りを出力してください。

入出力例

入力 1

5 3
a
b
c
d
e
cad

出力 1

26

入力 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

出力 2

12451