Trie Sharding (Small)

A set of strings S can be stored in a trie. A trie is a rooted tree that holds exactly one node for every distinct prefix of the strings in S. The empty string counts as a prefix.

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

One server keeps all of S in a single trie. S has grown too large for the memory of one machine, so you want to spread S over N servers. Split S into disjoint, non-empty subsets $T_1, T_2, \dots, T_N$, and let server $i$ build a trie over the strings in $T_i$. The total number of nodes across the N tries may go up. Worse, you cannot control how the strings are split.

For example, split "AAA", "AAB", "AB", "B" across two servers so that one holds "AAA" and "B" while the other holds "AAB" and "AB". The first trie then needs 5 nodes ("", "A", "AA", "AAA", "B") and the second trie also needs 5 nodes ("", "A", "AA", "AAB", "AB"). That is 10 nodes in total, against the 7 nodes a single server would need.

Given S and N, find the largest possible total number of nodes and the number of splits that reach it. The N servers are distinct: if a string lies in $T_i$ in one split and in $T_j$ ($i \neq j$) in another, the two splits count as different. Print the number of splits modulo 1,000,000,007.

The first line contains the number of test cases T. The first line of each test case contains two space-separated integers M and N. The next M lines each contain one string of S.

Limits

• $1 \le T \le 100$
• $1 \le M \le 8$
• $1 \le N \le 4$
• $N \le M$
• Every string in S consists of upper case English letters and has length 1 to 10.
• All strings in S are distinct.

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