Trie Sharding

A set of strings $S$ can be stored compactly in a trie. A trie is a rooted tree that has exactly one node for every distinct prefix of the strings in $S$, counting the empty prefix.

For example, if $S$ is "AAA", "AAB", "AB", "B", the trie has 7 nodes, one for each of the prefixes "", "A", "AA", "AAA", "AAB", "AB", "B".

One server holds all of $S$ in a single trie. $S$ has grown too large to fit in that server's memory, so $S$ is spread over $N$ servers instead. $S$ is split into disjoint non-empty subsets $T_1, T_2, \dots, T_N$, and server $i$ builds a trie that holds only the strings in $T_i$. The total number of nodes over all $N$ tries can then be larger than the number of nodes in the single trie, and the way the strings are split cannot be controlled.

Take the same four strings and split them over two servers, "AAA" and "B" on the first server, "AAB" and "AB" on the second. The first trie needs 5 nodes ("", "A", "AA", "AAA", "B") and the second trie also needs 5 nodes ("", "A", "AA", "AAB", "AB"). The two servers hold 10 nodes together, against the 7 nodes one server needs for all four strings.

Given $S$ and $N$, find the largest total number of nodes that a split can produce, and count the splits that reach it. The servers are distinguishable: if a string lies in $T_i$ in one split and in $T_j$ with $i \ne j$ in another split, the two splits are different. Report the count modulo 1,000,000,007.

The first line has the number of test cases $T$. Each test case starts with a line holding two integers $M$ and $N$ separated by a space. The next $M$ lines each hold one string of $S$.

Limits

• $1 \le T \le 100$
• $1 \le M \le 1000$
• $1 \le N \le 100$
• $N \le M$
• Every string of $S$ has 1 to 100 characters and uses upper case English letters only.
• The strings of $S$ are all distinct.

For each test case print one line in the form "Case #i: X Y", where $i$ is the test case number starting from 1, $X$ is the largest total number of nodes over all $N$ tries, and $Y$ is the number of splits whose total node count is $X$, taken modulo 1,000,000,007.