考虑 $n$ 个初始的小写字母字符串，其中没有任何一个字符串是其他任何字符串的前缀。 现在，考虑从中选择 $k$ 个字符串（每个字符串最多选一次），并将它们连接在一起。 你可以组成这么多复合字符串： $$n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1)$$ 考虑将通过此过程得到的所有复合字符串按字母顺序排序。给定一个测试复合字符串，保证它在列表中。求该测试复合字符串在所有复合字符串的字母排序列表中的位置，结果对 $10^9 + 7$ 取模。列表中的第一个复合字符串位置为 1。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个测试用例的第一行包含两个整数，先是 $n$，然后是 $k$ ($1 \le k \le n$)，其中 $n$ 是初始字符串的数量，$k$ 是你选择用来组成复合字符串的初始字符串数量。 $n$ 和 $k$ 的上限受下文中字符串约束的限制。 接下来的 $n$ 行，每行包含一个字符串，由一个或多个小写字母 $a..z$ 组成。这些是 $n$ 个初始字符串。保证没有任何一个初始字符串是其他任何初始字符串的前缀。 最后一行包含另一个字符串，仅由小写字母 $a..z$ 组成。这是测试复合字符串，你需要找到它在排序列表中的位置。保证该测试复合字符串是由 $k$ 个不同的初始字符串连接而成的。 所有输入字符串（包括测试字符串）的总长度不超过 $10^6$ 个字符。

输出格式

输出一个整数，表示测试复合字符串在排序后的复合字符串列表中的位置。将此数字对 $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