서로 다른 부분 문자열 쿼리
시간 제한2초메모리 제한512 MB
문자열 뒤에 문자를 붙이고 앞에서 문자를 빼는 연산을 백만 번까지 수행하면서, 매 연산 직후 서로 다른 부분 문자열의 개수를 구한다.
문제
처음에 빈 문자열 가 있다. 다음 두 종류의 쿼리를 차례대로 수행하는 프로그램을 작성하시오.
+ c: 의 맨 뒤에 문자 를 추가한다. 는 알파벳 소문자이다.-: 의 맨 앞 글자를 제거한다.
각 쿼리를 수행한 직후 의 길이는 항상 양수이다.
쿼리를 하나 수행할 때마다 그 시점의 에 있는 서로 다른 부분 문자열의 개수를 구해야 한다.
입력
첫째 줄에 쿼리의 개수 가 주어진다. ()
둘째 줄부터 개의 줄에 쿼리가 한 줄에 하나씩 주어진다.
출력
각 쿼리를 수행한 직후 의 서로 다른 부분 문자열의 개수를 구하고, 이 값을 모든 쿼리에 대해 더한 합을 로 나눈 나머지를 출력한다.
힌트
첫 번째 예제에서 각 쿼리 직후의 상태는 다음과 같다.
- = a이다. 서로 다른 부분 문자열은 a로 1개이다.
- = ab이다. 서로 다른 부분 문자열은 a, b, ab로 3개이다.
- = aba이다. 서로 다른 부분 문자열은 a, b, ab, ba, aba로 5개이다.
- = abaa이다. 서로 다른 부분 문자열은 a, b, ab, ba, aa, aba, baa, abaa로 8개이다.
- = baa이다. 서로 다른 부분 문자열은 a, b, ba, aa, baa로 5개이다.
- = aa이다. 서로 다른 부분 문자열은 a, aa로 2개이다.
- = a이다. 서로 다른 부분 문자열은 a로 1개이다.
- = aa이다. 서로 다른 부분 문자열은 a, aa로 2개이다.
합은 이고, 이므로 답은 27이다.