트라이 샤딩

문자열 집합 S는 트라이에 효율적으로 저장할 수 있다. 트라이는 S의 모든 문자열에 대한 모든 접두사마다 중복 없이 하나의 노드를 갖는 루트가 있는 트리이다.

예를 들어 S가 "AAA", "AAB", "AB", "B"라면, 이에 해당하는 트라이는 접두사 "", "A", "AA", AAA", "AAB", "AB", "B"에 해당하는 7개의 노드를 포함한다.

나는 하나의 큰 트라이에 S를 담고 있는 서버를 가지고 있다. 안타깝게도 S가 매우 커져서 서버 하나의 메모리에 모든 것을 저장하기가 어려워졌다. 이 문제를 해결하기 위해 S를 N개의 별도 서버에 나누어 저장하려 한다. 구체적으로 S를 서로 겹치지 않는 공집합이 아닌 부분집합 $T_{1}$, $T_{2}$, ..., $T_{N}$로 나누고, 각 서버 i에는 $T_{i}$의 문자열만 포함하는 트라이를 구축한다. 이 방식의 단점은 N개 트라이 전체의 총 노드 수가 늘어날 수 있다는 것이다. 설상가상으로 문자열 집합이 어떻게 나뉘는지도 제어할 수 없다!

예를 들어 "AAA", "AAB", "AB", "B"를 두 서버로 나누어 한 서버에는 "AAA"와 "B"를, 다른 서버에는 "AAB", "AB"를 저장한다고 하자. 그러면 첫 번째 서버의 트라이에는 5개의 노드("", "A", "AA", "AAA", "B")가 필요하고, 두 번째 서버의 트라이에도 5개의 노드("", "A", "AA", "AAB", "AB")가 필요하다. 이 경우 서버 하나에 모든 것을 저장할 수 있었다면 필요했을 7개의 노드와 달리, 두 서버 전체에 총 10개의 노드가 필요하다.

문자열을 N개 서버에 할당한 결과가 주어졌을 때, 모든 서버에 걸친 최악의 총 노드 수와 그것이 발생할 가능성을 계산하고 싶다. 그러면 이 계획이 좋은지 아니면 너무 위험한지 판단할 수 있다.

S와 N이 주어질 때, 최종적으로 생길 수 있는 가장 큰 노드 수는 얼마인가? 또한 노드 수가 최대가 되도록 $T_{1}$, $T_{2}$, ..., $T_{N}$를 선택하는 방법은 몇 가지인가? N개의 서버는 서로 다르다는 점에 유의하라. 한 배치에서는 어떤 문자열이 $T_{i}$에 나타나고 다른 배치에서는 $T_{j}$ (i != j)에 나타난다면, 두 배치는 서로 다른 것으로 간주한다. 가능한 배치 수를 1,000,000,007로 나눈 나머지를 출력한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. S의 문자열은 영어 대문자로만 이루어진다. S의 모든 문자열은 서로 다르다. N ≤ M

작은 데이터 세트

시간 제한: 60초. 1 ≤ M ≤ 8 1 ≤ N ≤ 4 S의 각 문자열 길이는 1자 이상 10자 이하이다.

큰 데이터 세트

시간 제한: 120초. 1 ≤ M ≤ 1000 1 ≤ N ≤ 100 S의 각 문자열 길이는 1자 이상 100자 이하이다.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 M과 N을 포함하는 한 줄로 시작한다. 이어지는 M개의 줄에는 각각 S의 문자열 하나가 주어진다.

각 테스트 케이스마다 "Case #i: X Y"를 포함하는 한 줄을 출력한다. 여기서 i는 케이스 번호이며(1부터 시작한다), X는 모든 트라이를 합쳤을 때의 최악의 노드 수이고, Y는 N개 서버 전체의 노드 수가 X가 되도록 문자열을 서버에 할당하는 방법의 수를 1,000,000,007로 나눈 나머지이다.