Đếm nút cây tiền tố

Trong một dự án nghiên cứu về nén dữ liệu tại trung tâm siêu máy tính LQD, các nhà khoa học đang làm việc với một tập hợp \(S\) gồm \(n\) chuỗi nhị phân đặc biệt. Các chuỗi này chỉ chứa hai loại ký tự: 'a' và 'b'.

Một chuỗi \(A\) được gọi là một biến thể hoán vị của chuỗi \(B\) nếu chuỗi \(A\) có thể được tạo ra bằng cách thay đổi thứ tự các ký tự của chuỗi \(B\). Các nhà nghiên cứu quyết định mở rộng tập hợp \(S\) thành một tập hợp khổng lồ \(S'\) theo quy tắc: Với mỗi chuỗi \(S_i\) trong tập \(S\) ban đầu, tất cả các biến thể hoán vị của nó sẽ được thêm vào \(S'\).

Để quản lý tập hợp \(S'\), một cấu trúc dữ liệu cây tiền tố (Trie) được xây dựng. Nhắc lại, Trie là một cây có gốc, trong đó mỗi cạnh được gán một ký tự. Mỗi nút trong cây đại diện cho một tiền tố của một hoặc nhiều chuỗi trong tập hợp. Nút gốc đại diện cho chuỗi rỗng.

Nhiệm vụ của bạn là tính toán tổng số nút có trong cây Trie đại diện cho tất cả các chuỗi thuộc tập \(S'\). Vì kết quả có thể rất lớn, hãy đưa ra đáp án theo mô-đun \(10^9 + 7\).

Input

Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 20\)) --- số lượng chuỗi ban đầu trong tập \(S\).

Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi \(S_i\) (\(1 \le |S_i| \le 10^5\)). Các chuỗi chỉ bao gồm các ký tự 'a' và 'b'.

Output

In ra một số nguyên duy nhất là tổng số nút của cây Trie sau khi chia lấy dư cho \(10^9 + 7\).

Example

1
abaa

14

2
abb
aaa

11

4
aa
ab
bb
aba

10

Scoring

• Subtask 1 (20% số điểm): \(|S_i| \le 20\).
• Subtask 2 (20% số điểm): \(n = 1, |S_i| \le 10^3\).
• Subtask 3 (15% số điểm): \(n = 2, |S_i| \le 10^3\).
• Subtask 4 (10% số điểm): \(|S_i| \le 10^3\).
• Subtask 5 (15% số điểm): \(n = 1, |S_i| \le 10^5\).
• Subtask 6 (10% số điểm): \(n = 2, |S_i| \le 10^5\).
• Subtask 7 (10% số điểm): Không có ràng buộc gì thêm.