题目描述

考虑 $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 完成