题目描述

考虑 $n$ 个由小写字母组成的初始字符串，且没有哪个初始字符串是另一个初始字符串的前缀。现在，从中选择 $k$ 个字符串（每个字符串最多选一次），并将它们按顺序拼接起来。通过这种方式，你可以得到以下数量的复合字符串：

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

考虑将所有通过此过程得到的复合字符串按字典序排序。给定一个测试复合字符串，它保证出现在这个列表中。请找出该测试复合字符串在排序后的所有复合字符串列表中的位置（从 1 开始编号），并对 $10^9 + 7$ 取模。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个测试用例的第一行包含两个整数，首先是 $n$，然后是 $k$（$1 \leq k \leq n$），其中 $n$ 是初始字符串的数量，$k$ 是构成复合字符串时选择的初始字符串个数。$n$ 和 $k$ 的上限受限于后续字符串的长度约束。

接下来的 $n$ 行，每行包含一个字符串，由一个小写字母或多个小写字母组成。这些是 $n$ 个初始字符串。保证没有哪个初始字符串是另一个初始字符串的前缀。

最后一行包含另一个字符串，仅由小写字母组成。这就是测试复合字符串，你需要找出它在排序列表中的位置。保证该测试复合字符串是由 $k$ 个互不相同的初始字符串拼接而成的。

所有输入字符串（包括测试字符串）的总长度不超过 $10^6$ 个字母。

输出格式

输出一个整数，表示测试复合字符串在排序后的复合字符串列表中的位置。输出该数字对 $10^9 + 7$ 取模的结果。

5 3
a
b
c
d
e
cad

26

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

12451

提示

翻译由 DeepSeek V3.2 完成