3080번 - 아름다운 이름 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 1977 | 402 | 261 | 19.177% |
문제
상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다.
같은 알파벳 순서로 시작하는 두 이름의 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다.
예를 들어, 두 이름이 MARTHA와 MARY는 모두 MAR로 시작한다. 따라서, 그 두 단어 사이에는 MARCO나 MARVIN과 같이 MAR로 시작하는 이름만이 존재할 수 있다. (MAY는 그 사이에 있을 수 없다)
상근이의 규칙을 지키면서 학생들 이름의 순서를 정하는 방법의 수를 구하는 프로그램을 작성하시오. 참고로 사전순으로 정렬하면, 항상 상근이의 규칙을 지킬 수 있다.
입력
첫째 줄에 이름의 수 N이 주어진다. (3 ≤ N ≤ 3000)
다음 N개 줄에는 이름이 한 줄에 하나씩 주어진다. 이름의 길이는 3000보다 작으며, 알파벳 대문자로만 이루어져 있다. 모든 이름은 중복되지 않는다.
출력
상근이의 규칙을 지키면서 순서를 정하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
예제 입력 1
3 IVO JASNA JOSIPA
예제 출력 1
4
예제 입력 2
5 MARICA MARTA MATO MARA MARTINA
예제 출력 2
24
예제 입력 3
4 A AA AAA AAAA
예제 출력 3
8
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호