Xét $n$ xâu ban đầu gồm các chữ cái thường, trong đó không có xâu ban đầu nào là tiền tố của một xâu ban đầu khác. Bây giờ, xét việc chọn $k$ xâu trong số đó (mỗi xâu không được chọn quá một lần) rồi nối chúng lại với nhau. Số xâu ghép có thể tạo ra theo cách này là:

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

Xét việc sắp xếp tất cả các xâu ghép có thể tạo ra bằng quá trình này theo thứ tự từ điển. Bạn được cho một xâu ghép cần xét, được đảm bảo có trong danh sách này. Hãy tìm vị trí của xâu ghép đó trong danh sách tất cả các xâu ghép đã sắp xếp theo thứ tự từ điển, lấy modulo $10^9+7$. Xâu ghép đầu tiên trong danh sách nằm ở vị trí $1$.

Dữ liệu vào

Mỗi dữ liệu vào gồm một bộ kiểm thử. Lưu ý rằng chương trình của bạn có thể được chạy nhiều lần với các dữ liệu vào khác nhau. Mỗi bộ kiểm thử bắt đầu bằng một dòng chứa hai số nguyên, trước tiên là $n$, sau đó là $k$ ($1 \le k \le n$), trong đó $n$ là số xâu ban đầu và $k$ là số xâu ban đầu được chọn để tạo các xâu ghép. Cận trên của $n$ và $k$ được giới hạn bởi các ràng buộc về xâu trong những đoạn dưới đây.

Mỗi dòng trong $n$ dòng tiếp theo chứa một xâu gồm một hoặc nhiều chữ cái thường a–z. Đây là $n$ xâu ban đầu. Đảm bảo rằng không có xâu ban đầu nào là tiền tố của một xâu ban đầu khác.

Cuối cùng, dòng cuối chứa một xâu khác, chỉ gồm các chữ cái thường a–z. Đây là xâu ghép cần xét mà bạn phải tìm vị trí trong danh sách đã sắp xếp. Đảm bảo rằng xâu ghép này là kết quả nối $k$ xâu ban đầu khác nhau.

Tổng độ dài của tất cả các xâu đầu vào, kể cả xâu cần xét, không vượt quá $10^6$ chữ cái.

Dữ liệu ra

In ra một số nguyên là vị trí mà xâu ghép cần xét xuất hiện trong danh sách các xâu ghép đã sắp xếp. In số này lấy modulo $10^9+7$.

Ví dụ

Dữ liệu vào 1

5 3
a
b
c
d
e
cad

Dữ liệu ra 1

26

Dữ liệu vào 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

Dữ liệu ra 2

12451