트라이 샤딩

문자열 집합 $S$는 트라이 하나에 모아서 저장할 수 있다. 트라이는 뿌리 있는 트리로, $S$에 속한 문자열의 서로 다른 접두사마다 노드가 정확히 하나씩 있다. 빈 접두사도 노드 하나를 차지한다.

예를 들어 $S$가 "AAA", "AAB", "AB", "B"이면 트라이의 노드는 7개다. 접두사 "", "A", "AA", "AAA", "AAB", "AB", "B"에 각각 노드가 하나씩 대응한다.

서버 한 대가 $S$ 전체를 트라이 하나로 들고 있다. $S$가 너무 커져서 그 서버의 메모리에 들어가지 않으므로 $S$를 서버 $N$대에 나눠 저장한다. $S$를 서로 겹치지 않고 비어 있지도 않은 부분집합 $T_1, T_2, \dots, T_N$으로 쪼개고, $i$번 서버는 $T_i$에 속한 문자열만 담은 트라이를 만든다. 이렇게 하면 트라이 $N$개의 노드 수 합이 원래 트라이의 노드 수보다 많아지기도 한다. 게다가 문자열이 어떻게 쪼개질지는 정하지 못한다.

같은 문자열 네 개를 서버 두 대에 나눠, 첫째 서버에 "AAA"와 "B"를, 둘째 서버에 "AAB"와 "AB"를 담아 보자. 첫째 트라이는 노드 5개("", "A", "AA", "AAA", "B")가 필요하고 둘째 트라이도 노드 5개("", "A", "AA", "AAB", "AB")가 필요하다. 두 서버가 합쳐서 노드 10개를 쓰는 셈이고, 한 대에 넷을 모두 담을 때 필요한 7개보다 많다.

$S$와 $N$이 주어질 때 쪼개는 방법이 만들 수 있는 노드 수 합의 최댓값과, 그 최댓값에 도달하는 방법의 수를 구하라. 서버는 서로 구별한다. 어떤 문자열이 한 방법에서는 $T_i$에 들어가고 다른 방법에서는 $T_j$($i \ne j$)에 들어가면 두 방법은 서로 다르다. 방법의 수는 1,000,000,007로 나눈 나머지를 구한다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $M$과 $N$이 공백을 사이에 두고 주어진다. 이어지는 $M$개의 줄에 $S$에 속한 문자열이 한 줄에 하나씩 주어진다.

제한

• $1 \le T \le 100$
• $1 \le M \le 1000$
• $1 \le N \le 100$
• $N \le M$
• $S$의 문자열은 길이가 1 이상 100 이하이고 영어 대문자로만 이루어진다.
• $S$의 문자열은 모두 서로 다르다.

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