一个字符串集合 $S$ 可以高效地存储在字典树（trie）中。字典树是一棵有根树，对于 $S$ 中每个字符串的每一个前缀，树中都有且仅有一个对应的节点（不重复）。

例如，如果 $S$ 为 "AAA", "AAB", "AB", "B"，对应的字典树将包含 7 个节点，分别对应前缀 "", "A", "AA", "AAA", "AAB", "AB" 和 "B"。

我有一台服务器，其中包含一个存储了 $S$ 的大型字典树。不幸的是，$S$ 变得非常大，我无法将所有内容都存放在一台服务器的内存中。为了解决这个问题，我想将 $S$ 分散存储在 $N$ 台独立的服务器上。具体来说，$S$ 将被划分为 $N$ 个不相交且非空的子集 $T_1, T_2, \dots, T_N$，并且在每台服务器 $i$ 上，我将构建一个仅包含 $T_i$ 中字符串的字典树。这种方法的缺点是所有 $N$ 台服务器上的字典树节点总数可能会增加。更糟糕的是，我无法控制字符串集合是如何划分的！

例如，假设 "AAA", "AAB", "AB", "B" 被分到两台服务器上，一台包含 "AAA" 和 "B"，另一台包含 "AAB" 和 "AB"。那么第一台服务器上的字典树需要 5 个节点 ("", "A", "AA", "AAA", "B")，第二台服务器上的字典树也需要 5 个节点 ("", "A", "AA", "AAB", "AB")。在这种情况下，两台服务器总共需要 10 个节点，而如果能将所有内容放在一台服务器上，则只需要 7 个节点。

给定一种将字符串分配给 $N$ 台服务器的方案，我想计算所有服务器上字典树节点总数的最坏情况，以及这种情况发生的可能性。这样我就可以决定我的计划是可行的还是风险太高。

给定 $S$ 和 $N$，我最终可能得到的最大节点数是多少？此外，有多少种划分 $T_1, T_2, \dots, T_N$ 的方式能达到这个最大节点数？注意，$N$ 台服务器是不同的——如果一个字符串在一种排列中出现在 $T_i$ 中，而在另一种排列中出现在 $T_j$ ($i \neq j$) 中，则这两种排列被视为不同。请输出可能的划分方案数除以 $1,000,000,007$ 的余数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个空格分隔的整数：$M$ 和 $N$。接下来的 $M$ 行，每行包含 $S$ 中的一个字符串。

输出格式

对于每个测试用例，输出一行 "Case #$i$: $X$ $Y$"，其中 $i$ 是用例编号（从 1 开始），$X$ 是所有字典树中节点总数的最坏情况，$Y$ 是将字符串分配给 $N$ 台服务器使得节点总数为 $X$ 的方案数（模 $1,000,000,007$）。

数据范围

$1 \le T \le 100$。 $S$ 中的字符串仅包含大写英文字母。 $S$ 中的字符串互不相同。 $N \le M$。

小数据集

$1 \le M \le 8$ $1 \le N \le 4$ $S$ 中每个字符串的长度在 1 到 10 之间（含边界）。

大数据集

$1 \le M \le 1000$ $1 \le N \le 100$ $S$ 中每个字符串的长度在 1 到 100 之间（含边界）。

样例

样例输入 1

2
4 2
AAA
AAB
AB
B
5 2
A
B
C
D
E

样例输出 1

Case #1: 10 8
Case #2: 7 30