Thầy Herkabe đã quyết định xếp hạng lại học sinh của mình. Lần này, anh ấy muốn danh sách của mình cũng phải đẹp mắt về mặt thẩm mỹ, vì vậy anh ấy đã quyết định rằng những cái tên tương tự (những tên bắt đầu bằng cùng một chữ cái hoặc chuỗi các chữ cái) phải gần nhau trong danh sách. Vì vậy, ông đã nghĩ ra quy tắc sau:

Đối với mỗi hai tên trong danh sách bắt đầu bằng cùng một chuỗi chữ cái, tất cả các tên giữa chúng trong danh sách cũng phải bắt đầu bằng chuỗi chữ cái đó.

Ví dụ, hãy xem xét tên MARTHA và MARY (các nhân vật trong một câu chuyện hay). Cả hai đều bắt đầu bằng chuỗi MAR, vì vậy các tên bắt đầu bằng cùng một chuỗi (như MARCO và MARVIN) có thể xuất hiện ở giữa (nhưng không phải MAY chẳng hạn).

Lưu ý rằng thứ tự được sắp xếp theo từ điển luôn thỏa mãn quy tắc này, nhưng nó không phải là thứ tự hợp lệ duy nhất. Nhiệm vụ của bạn là xác định có bao nhiêu thứ tự khác nhau thỏa mãn quy tắc, tức là giáo viên Herkabe có bao nhiêu lựa chọn cho danh sách xếp hạng của mình.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(3 \le N \le 3000)~, số lượng tên.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa một tên: một chuỗi gồm từ ~1~ đến ~3000~ các chữ cái tiếng Anh viết hoa. Các tên đều khác biệt và được đưa ra không theo thứ tự cụ thể.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa số lượng danh sách xếp hạng có thể có theo yêu cầu chia dư cho ~1 000 000 007~.

Scoring

Trong dữ liệu kiểm tra có tổng điểm là ~60~ điểm thì số ~N~ sẽ nhỏ hơn ~10~.

Sample Input 1

3
IVO
JASNA
JOSIPA

Sample Output 1

4

Sample Input 2

5
MARICA
MARTA
MATO
MARA
MARTINA

Sample Output 2

24

Sample Input 2

4
A
AA
AAA
AAAA

Sample Output 2

8