기차 차량 재배열

Yahya는 아주 영리한 아이이므로, 장난감을 가지고 놀 때 머릿속에 흥미로운 질문이 많이 떠오른다. 오늘의 문제는 아버지가 한쪽 면에 소문자 하나가 적힌 기차 차량 세트를 가져다주면서 생겨났다.

선물을 처음 보았을 때 그는 기뻐하며 특별한 목표 없이 차량들을 서로 연결해 가지고 놀기 시작했다. 하지만 얼마 지나지 않아 목표 없이 노는 것에 (늘 그렇듯이) 싫증이 났다. 그래서 새롭고 흥미로운 문제를 정의하기로 했다.

문제는 현재 그에게 연결된 차량 묶음이 N개 있다는 것이다. 연결된 각 차량 묶음은 소문자 문자열로 나타낼 수 있다. 그는 N개의 차량 묶음을 모두 연결해 하나의 유효한 기차를 만드는 방법의 수를 세고 싶다. 같은 문자가 나타나는 모든 위치가 서로 인접해 있을 때 기차가 유효하다.

앞의 그림은 Yahya가 차량 "ab", "bc", "cd"를 연결하여 유효한 기차 "ab bc cd"를 만들 수 있는 한 가지 방법이다. 이를 "cd ab bc" 순서로 연결했다면 유효하지 않았을 것이다. "c" 문자들이 서로 인접하지 않기 때문이다.

분명히 알겠지만 Yahya가 풀기에는 쉽지 않은 문제이므로, 그는 당신의 도움이 필요하다(그리고 당신이 도와줄 것이라고 확신한다!). 설명은 이것으로 끝이다. 이제 Yahya를 도와주자!

참고: 글자는 차량의 한쪽 면에만 적혀 있으므로 차량을 뒤집을 수 없다. 예를 들어 차량에 "ab"가 적혀 있다면, 이를 "ba"로 읽히도록 바꿀 수 없다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 연결된 차량 묶음의 길이는 1 ≤ ≤ 100이다.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 10.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 연결된 차량 묶음의 수를 나타내는 정수 N 하나가 주어진다. 다음 줄에는 하나의 공백으로 구분된 N개의 문자열이 주어진다. 주어지는 각 문자열은 연결된 차량 묶음을 나타내며 영어 소문자로만 구성된다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 유효한 기차를 얻는 서로 다른 방법의 수이다. 이 수는 매우 클 수 있으므로 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 설명

첫 번째 경우에는 문자열 "ab"를 "bbbc"에 연결하고, 다시 "cd"에 이 순서대로 연결하여 유효한 기차를 만드는 방법이 하나뿐이다.

두 번째 경우에는 유효한 기차를 만드는 방법이 4가지 있다. 문자열 "aa"로 나타나는 서로 다른 연결된 차량 묶음이 두 개 있으므로, 이 두 문자열의 순서를 정하고 하나의 연결된 차량 묶음 "aaaa"로 합치는 방법은 두 가지이다. 또한 차량 묶음 "bc"와 "c"의 순서를 정해 "bcc"로 만드는 방법은 하나뿐이다. 그 후 "aaaa"와 "bcc"의 순서는 서로 다른 두 가지 방법으로 정할 수 있다. 따라서 유효한 기차를 만드는 방법은 모두 2*2 = 4가지이다.

세 번째 예제의 경우 유효한 기차를 만들 수 있는 방법이 없다. 가능한 두 가지 방법인 "abc"+"bcd" 또는 "bcd"+"abc" 중 어느 방식으로 연결하더라도, "b"와 "c"의 두 글자가 연속하지 않기 때문이다.