MOG
Spanish
|
English

Matcom Online Grader

MOG Training #7

Ended

E - Prefix Free Code

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

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 ... \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 \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 $\texttt{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 $\texttt{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 test(s)

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