기차 칸 재배열 (작은 입력)

야히아는 호기심이 많은 아이라서, 장난감을 가지고 놀다 보면 재미있는 질문을 자주 떠올린다. 오늘의 문제는 아버지가 장난감 기차 칸 한 세트를 사 주면서 시작됐다. 각 칸의 한쪽 면에는 영어 소문자 한 글자가 적혀 있다.

처음에는 아무 목표 없이 칸을 이어 붙이며 놀았지만 금세 싫증이 났고, 그래서 새 문제를 스스로 만들었다.

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

위 그림은 "ab", "bc", "cd"를 "ab bc cd" 순서로 이어 올바른 기차를 만든 방법이다. "cd ab bc" 순서로 이었다면 글자 "c"가 떨어지므로 올바르지 않다.

묶음은 서로 구별한다. 문자열이 같은 묶음이 두 개 있어도 놓는 순서가 다르면 서로 다른 방법으로 센다.

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

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

제한

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

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

첫 번째 예제에서는 "ab", "bbbc", "cd"를 이 순서로 잇는 한 가지만 올바른 기차가 된다.

두 번째 예제에서는 방법이 4가지이다. 문자열이 "aa"인 묶음이 두 개 있으므로 이 둘을 배열해 "aaaa"를 만드는 방법이 2가지이고, "bc"와 "c"를 이어 "bcc"를 만드는 방법은 1가지이다. 그 다음 "aaaa"와 "bcc"를 배열하는 방법이 2가지이므로 모두 $2 \times 2 = 4$가지이다.

세 번째 예제에서는 올바른 기차를 만들 수 없다. "abc"+"bcd"로 이어도 "bcd"+"abc"로 이어도 글자 "b"와 "c"가 떨어지기 때문이다.