题目描述

Consider $n$ initial strings of lower case letters, where no initial string is a prefix of any other initial string. Now, consider choosing $k$ of the strings (no string more than once), and concatenating them together. You can make this many such composite strings:

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

Consider sorting all of the composite strings you can get via this process in alphabetical order. You are given a test composite string, which is guaranteed to belong on this list. Find the position of this test composite string in the alphabetized list of all composite strings, modulo $10^9 + 7$. The first composite string in the list is at position 1.

输入格式

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers, first $n$ and then $k$ ($1 \leq k \leq n$), where $n$ is the number of initial strings, and $k$ is the number of initial strings you choose to form composite strings. The upper bounds of $n$ and $k$ are limited by the constraints on the strings, in the following paragraphs.

Each of the next $n$ lines will contain a string, which will consist of one or more lower case letters $a\dots z$. These are the $n$ initial strings. It is guaranteed that none of the initial strings will be a prefix of any other of the initial strings.

Finally, the last line will contain another string, consisting of only lower case letters $a\dots z$. This is the test composite string, the position of which in the sorted list you must find. This test composite string is guaranteed to be a concatenation of $k$ unique initial strings.

The sum of the lengths of all input strings, including the test string, will not exceed $10^6$ letters.

输出格式

Output a single integer, which is the position in the list of sorted composite strings where the test composite string occurs. Output this number modulo $10^9 + 7$.

5 3
a
b
c
d
e
cad

26

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

12451