Pertimbangkan $n$ string awal yang terdiri dari huruf kecil, dengan tidak ada string awal yang merupakan prefiks dari string awal lainnya. Sekarang, pilih $k$ string (setiap string paling banyak sekali), lalu gabungkan semuanya. Banyaknya string gabungan yang dapat dibentuk adalah:

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

Urutkan semua string gabungan yang dapat diperoleh melalui proses ini menurut urutan alfabet. Anda diberi sebuah string gabungan uji yang dijamin terdapat dalam daftar tersebut. Tentukan posisi string gabungan uji ini dalam daftar semua string gabungan yang telah diurutkan menurut alfabet, modulo $10^9+7$. String gabungan pertama dalam daftar berada pada posisi $1$.

Masukan

Setiap masukan terdiri dari satu kasus uji. Perhatikan bahwa program Anda dapat dijalankan beberapa kali dengan masukan yang berbeda. Setiap kasus uji diawali dengan satu baris berisi dua bilangan bulat, pertama $n$ lalu $k$ ($1 \le k \le n$), dengan $n$ adalah banyaknya string awal dan $k$ adalah banyaknya string awal yang dipilih untuk membentuk string gabungan. Batas atas $n$ dan $k$ ditentukan oleh batasan string dalam paragraf-paragraf berikut.

Masing-masing dari $n$ baris berikutnya berisi sebuah string yang terdiri dari satu atau lebih huruf kecil a hingga z. Inilah $n$ string awal tersebut. Dijamin bahwa tidak ada string awal yang merupakan prefiks dari string awal lainnya.

Terakhir, baris terakhir berisi sebuah string lain yang hanya terdiri dari huruf kecil a hingga z. Inilah string gabungan uji yang posisinya dalam daftar terurut harus Anda tentukan. String gabungan uji ini dijamin merupakan gabungan dari $k$ string awal yang berbeda.

Jumlah panjang seluruh string masukan, termasuk string uji, tidak melebihi $10^6$ huruf.

Keluaran

Keluarkan sebuah bilangan bulat, yaitu posisi string gabungan uji dalam daftar string gabungan yang telah diurutkan. Keluarkan bilangan ini modulo $10^9+7$.

Contoh

Masukan 1

5 3
a
b
c
d
e
cad

Keluaran 1

26

Masukan 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

Keluaran 2

12451