기차 칸 재배열 (라지)

야히아는 장난감을 가지고 놀 때마다 재미있는 질문을 떠올린다. 오늘의 문제는 아버지가 기차 칸 장난감 한 상자를 사 오면서 시작됐다. 칸마다 한쪽 면에 영어 소문자가 하나씩 적혀 있다.

처음에는 아무 목표 없이 칸을 이리저리 이어 붙이며 놀았지만 곧 싫증이 나서 새로운 문제를 만들기로 했다.

지금 야히아가 가진 것은 이미 서로 이어진 칸 묶음 $N$개다. 묶음 하나는 소문자로 이루어진 문자열로 나타낼 수 있다. 야히아는 이 $N$개의 묶음을 한 줄로 모두 이어 붙여 올바른 기차 하나를 만드는 방법이 몇 가지인지 세려고 한다. 같은 문자가 적힌 칸이 모두 서로 붙어 있으면 그 기차는 올바르다.

위 그림은 "ab", "bc", "cd" 세 묶음을 이어 붙여 올바른 기차 "ab bc cd"를 만든 예다. "cd ab bc" 순서로 이었다면 'c'가 적힌 칸 두 개가 떨어지므로 올바르지 않다.

문자열이 같은 묶음이라도 서로 다른 묶음으로 구별한다. 두 묶음의 자리를 맞바꾼 배치는 서로 다른 방법으로 센다.

글자는 칸의 한쪽 면에만 적혀 있으므로 묶음을 뒤집을 수 없다. 예를 들어 "ab"라고 적힌 묶음을 "ba"로 바꿀 수 없다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 이어진 칸 묶음의 개수 $N$이 주어진다. 다음 줄에는 $N$개의 문자열이 공백 하나로 구분되어 주어진다. 각 문자열은 묶음 하나를 나타내며 영어 소문자로만 이루어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 100$
• 각 문자열의 길이는 $1$ 이상 $100$ 이하다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 올바른 기차를 만드는 서로 다른 방법의 수다. 이 값이 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력의 첫 번째 테스트 케이스에서는 "ab", "bbbc", "cd"를 이 순서로 잇는 방법 하나뿐이다.

두 번째 테스트 케이스의 답은 4다. "aa"라고 적힌 묶음이 둘 있으므로 이 둘을 이어 "aaaa"를 만드는 순서가 두 가지다. "bc"와 "c"는 "bcc"가 되는 한 가지 순서뿐이다. 그다음 "aaaa"와 "bcc"를 놓는 순서가 두 가지이므로 모두 $2 \times 2 = 4$가지다.

세 번째 테스트 케이스에서는 "abc"+"bcd"로 이어도 "bcd"+"abc"로 이어도 'b'와 'c'가 각각 떨어지므로 올바른 기차를 만들 수 없다.