Yahya là một đứa trẻ thông minh, vì vậy tâm trí cậu luôn nảy sinh rất nhiều câu hỏi thú vị khi chơi với đồ chơi của mình. Bài toán hôm nay xuất hiện khi cha cậu mang về một bộ toa tàu đồ chơi, trong đó mỗi toa có một chữ cái tiếng Anh viết thường ở một mặt.

Khi mới nhận được món quà, cậu rất vui và bắt đầu chơi bằng cách nối các toa tàu lại với nhau mà không có mục tiêu cụ thể nào. Nhưng sau một thời gian, cậu cảm thấy chán (như thường lệ). Vì vậy, cậu quyết định định nghĩa một bài toán mới thú vị.

Bài toán là cậu hiện có \(N\) bộ toa tàu đã được nối sẵn. Cậu có thể biểu diễn mỗi bộ toa tàu đã nối này dưới dạng một chuỗi các chữ cái viết thường. Cậu muốn đếm số cách nối tất cả \(N\) bộ toa tàu này để tạo thành một đoàn tàu hợp lệ duy nhất. Một đoàn tàu được coi là hợp lệ nếu tất cả các lần xuất hiện của cùng một ký tự đều nằm cạnh nhau.

Hình trên là một cách Yahya có thể nối các bộ toa "ab", "bc" và "cd" để tạo thành một đoàn tàu hợp lệ: "ab bc cd". Nếu cậu nối chúng theo thứ tự "cd ab bc", đoàn tàu đó sẽ không hợp lệ: các ký tự "c" sẽ không nằm cạnh nhau.

Chắc chắn bạn đã nhận thấy đây không phải là một bài toán dễ giải đối với Yahya, vì vậy cậu ấy cần sự giúp đỡ của bạn! Hãy đi và giúp Yahya!

Lưu ý: các chữ cái chỉ được viết trên một mặt của toa tàu, vì vậy bạn không thể đảo ngược chúng. Ví dụ, nếu một toa tàu có chữ "ab" viết trên đó, nó không thể thay đổi thành "ba".

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Dòng đầu tiên của mỗi bộ thử nghiệm chứa một số nguyên duy nhất \(N\), số lượng bộ toa tàu đã nối. Dòng tiếp theo chứa \(N\) chuỗi cách nhau bởi một khoảng trắng. Mỗi chuỗi đại diện cho một bộ toa tàu đã nối và chỉ bao gồm các chữ cái tiếng Anh viết thường.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số cách khác nhau để có được một đoàn tàu hợp lệ. Vì con số này có thể rất lớn, hãy xuất kết quả theo modulo 1,000,000,007.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le\) Độ dài mỗi chuỗi toa tàu \(\le 100\).

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3
ab bbbc cd
4
aa aa bc c
2
abc bcd

Case #1: 1
Case #2: 4
Case #3: 0

Nguồn

Google Code Jam 2014, Vòng 1C, bài Reordering Train Cars.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.