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:

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\).

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.

Example

Test 1

Input

1
abaa

Output

14

Note

Với xâu abaa, ta tạo được các xâu hoán vị tương ứng như sau:

1. aaab
2. aaba
3. abaa
4. baaa

Từ đây, ta dựng được cây trie gồm \(14\) nút.

Test 2

Input

2
abb
aaa

Output

11

Note

Với mỗi xâu trong tập \(S\), ta tạo được các xâu hoán vị tương ứng như sau:

• abb \(\to\) abb, bab, bba
• aaa \(\to\) aaa

Từ đây, ta dựng được cây trie gồm \(11\) nút.

Test 3

Input

4
aa
ab
bb
aba

Output

10

Note

Với mỗi xâu trong tập \(S\), ta tạo được các xâu hoán vị tương ứng như sau:

• aa \(\to\) aa
• ab \(\to\) ab, ba
• bb \(\to\) bb
• aba \(\to\) aba, aab, baa

Từ đây, ta dựng được cây trie gồm \(10\) nút.