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:
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 |