Hide

Problem E
Prefix Free Code

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$.

Input

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 \le k \le 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..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..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

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$.

Sample Input 1 Sample Output 1
5 3
a
b
c
d
e
cad
26
Sample Input 2 Sample Output 2
8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin
12451

Please log in to submit a solution to this problem

Log in