아름다운 이름
시간 제한1초메모리 제한512 MB
공통 접두사를 가진 이름들이 항상 연속 구간을 이루도록 배치하는, 서로 다른 N개 이름의 순서 개수를 1,000,000,007로 나눈 나머지로 구하는 문제입니다.
문제
한 선생님은 학생들의 이름을 한 줄로 나열하려고 한다. 이름의 순서가 아름다우려면 다음 조건을 만족해야 한다.
어떤 문자열로 시작하는 이름들을 생각했을 때, 그 이름들은 전체 순서에서 하나의 연속한 구간을 이루어야 한다. 즉, 같은 접두사로 시작하는 두 이름 사이에는 그 접두사로 시작하는 이름만 놓일 수 있다.
주어진 모든 학생 이름을 아름다운 순서로 나열하는 방법의 수를 구하라.
입력
첫째 줄에 이름의 수 N이 주어진다. (3 <= N <= 3000)
다음 N개의 줄에는 이름이 한 줄에 하나씩 주어진다. 각 이름의 길이는 3000보다 작고, 알파벳 대문자로만 이루어져 있다. 모든 이름은 서로 다르다.
출력
아름다운 순서로 이름을 나열하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.