Trie

Cho tập hợp \(S\) gồm \(n\) xâu kí tự: \(S_1, S_2, \dots, S_n\). Kí tự trong các xâu này có thể là a hoặc b.

Một xâu \(A\) được gọi là xâu hoán vị của xâu \(B\), nếu ta có thể tạo ra được xâu \(A\) bằng cách sắp xếp lại các kí tự của xâu \(B\). Hãy tạo tập hợp \(S'\) theo nguyên tắc sau: với mỗi xâu \(S_i\) \((1 \le i \le n)\), ta thêm tất cả các xâu hoán vị của \(S_i\) vào \(S'\). Nói cách khác, \(S'\) là tập hợp các xâu hoán vị của \(n\) xâu thuộc \(S\).

Ta tiến hành dựng cây trie của tập xâu \(S'\) vừa tạo. Hãy cho biết cây trie này có bao nhiêu nút.

Nhắc lại về Trie

**Trie** là một cấu trúc dữ liệu dạng cây dùng để lưu trữ một danh sách các xâu với bộ kí tự hữu hạn, cho phép việc lưu trữ các xâu hiệu quả có tiền tố giống nhau.

Cây trie được dựng theo nguyên tắc: mỗi nút liên kết với một xâu ký tự sao cho các xâu ký tự của tất cả các nút con của một nút đều có chung một tiền tố, chính là xâu ký tự của nút đó. Nút gốc tương ứng với xâu ký tự rỗng.

Ví dụ, với các xâu `aba`, `abb`, `acb`, ta dựng được một cây trie gồm $7$ nút như sau:

\begincenter

\endcenter

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 20)\) là số lượng xâu trong tập \(S\).

• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S_i\) \((1 \le |S_i| \le 10^5)\), các kí tự của xâu chỉ có thể là a hoặc b.

Output

• In ra một số nguyên duy nhất là phần dư của đáp án bài toán khi chia 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| \leq 20\).

• Subtask \(2\) (\(20\%\) số điểm): \(n = 1, |S_i| \leq 10^3\).

• Subtask \(3\) (\(15\%\) số điểm): \(n = 2, |S_i| \leq 10^3\).

• Subtask \(4\) (\(10\%\) số điểm): \(|S_i| \leq 10^3\).

• Subtask \(5\) (\(15\%\) số điểm): \(n = 1\).

• Subtask \(6\) (\(10\%\) số điểm): \(n = 2\).

• Subtask \(7\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.