트라이 샤딩 (작은 입력)

문자열 집합 S는 트라이(trie)에 저장할 수 있다. 트라이는 뿌리 있는 트리이고, S에 속한 문자열의 서로 다른 접두사마다 노드가 정확히 하나씩 있다. 빈 문자열도 접두사로 센다.

예를 들어 S가 "AAA", "AAB", "AB", "B"라면 트라이는 "", "A", "AA", "AAA", "AAB", "AB", "B"에 대응하는 노드 7개로 이루어진다.

서버 한 대가 S 전체를 트라이 하나로 들고 있다. S가 너무 커져서 한 대의 메모리에 다 들어가지 않으므로, S를 서버 N대에 나누어 저장하려고 한다. 즉 S를 서로소이면서 비어 있지 않은 부분집합 $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개보다 많다.

S와 N이 주어질 때 노드 수 합의 최댓값과, 그 최댓값이 나오는 분할의 개수를 구하라. 서버 N대는 서로 구별된다. 어떤 문자열이 한 분할에서는 $T_i$에 들어가고 다른 분할에서는 $T_j$($i \neq j$)에 들어가면, 두 분할은 다른 것으로 센다. 분할의 개수는 1,000,000,007로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 M과 N이 공백으로 구분되어 주어지고, 이어지는 M개 줄에 S의 문자열이 한 줄에 하나씩 주어진다.

제한

• $1 \le T \le 100$
• $1 \le M \le 8$
• $1 \le N \le 4$
• $N \le M$
• S의 문자열은 영어 대문자로만 이루어지고, 길이는 1 이상 10 이하이다.
• S의 문자열은 모두 서로 다르다.

각 테스트 케이스마다 "Case #i: X Y" 형식으로 한 줄씩 출력한다. i는 1부터 시작하는 테스트 케이스 번호, X는 모든 트라이의 노드 수 합의 최댓값, Y는 노드 수 합이 X가 되는 분할의 개수를 1,000,000,007로 나눈 나머지이다.