시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 182 40 32 25.806%

문제

상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다.

같은 알파벳 순서로 시작하는 두 이름의 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다.

예를 들어, 두 이름이 MARTHA와 MARY는 모두 MAR로 시작한다. 따라서, 그 두 단어 사이에는 MARCO나 MARVIN과 같이 MAR로 시작하는 이름이 있어야 한다. (MAY는 그 사이에 있을 수 없다)

상근이의 규칙을 지키면서 학생들 이름의 순서를 정하는 방법의 수를 구하는 프로그램을 작성하시오. 참고로 사전순으로 정렬하면, 항상 상근이의 규칙을 지킬 수 있다. 

입력

첫째 줄에 이름의 수 N이 주어진다. (3 ≤ N ≤ 3000)

다음 N개 줄에는 이름이 한 줄에 하나씩 주어진다. 이름의 길이는 3000보다 작으며, 알파벳 대문자로만 이루어져 있다. 모든 이름은 중복되지 않는다.

출력

상근이의 규칙을 지키면서 순서를 정하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

3
IVO
JASNA
JOSIPA

예제 출력

4

예제 입력 2

5
MARICA
MARTA
MATO
MARA
MARTINA

예제 출력 2

24

예제 입력 3

4
A
AA
AAA
AAAA

예제 출력 3

8

힌트