시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 1 1 (100%) 1
문제
선생 허카베는 다시 그의 학생들을 순위매기기 시작했다. 지금, 그는 그의 목록을 심미적으로 만족시키기 위해, 비슷한 이름(시작부분이 같은 글자 혹은 글자들로 이루어진)은 다른 하나랑 꼭 근접하도록 하고 싶다. 따라서, 그는 다음과 같은 규칙을 만들었다: 만약 목록내의 두 이름이 같은 문자열로 시작하면, 목록상에서 그 이름둘 사이에 있는 이름들 역시 그 문자열로 시작해야 한다. 예를들어, 이름 MARTHA와 MARY를 생각해보자. (아름다운 이야기의 캐릭터들) 그들은 모두 MAR로 시작한다. 그러므로 그것과 동일한 문자열로 시작하는(MARCO나 MARVIN같음){ 이름들은 그둘 사이에 있을 수 있다. (이 예제에서, MAY는 아니다.) 사전순 정렬은 이것을 만족함이 알려져있지만, 가능한 순서를 구하는것은 별 으미가 없다. 당신의 임무는 얼마나 많은 종류의 순서이 이 규칙을 만족하는지 이다. 말하자면, 허카베 선생의 순위표에 얼마나 많은 선택지가 있는지이다.
입력
첫번재 줄에 양의 정수 N (3<=N<=3000), 이름의 갯수가 주어진다. N개의 줄에는 각각 하나의 이름을 가지고 있다: 1에서 3천개의 (포함하는) 대문이 영문자들로 이루어져있다. 이름들은 모두 다르고 특별한 순서는 아니다.
출력
첫번재 줄에 단하나의 줄로 가능한 순위표의 경우의 수를, 1 000 000 007로 나눈 나머지를 출력한다.
힌트
배점형식 테스트 데이터중 60점은 , N이 10보다 작다. 입력예제1 ``` 3 IVO JASNA JOSIPA ``` 출력예제1 ``` 4 ``` 입력예제2 ``` 5 MARICA MARTA MATO MARA MARTINA ``` 출력예제2 ``` 24 ``` 입력예제3 ``` 4 A AA AAA AAAA ``` 출력예제3 ``` 8 ```