14436번 - 서로 다른 부분 문자열 쿼리

문제

비어있는 문자열 S가 있다. 이때, 아래와 같이 쿼리를 수행하는 프로그램을 작성하시오.

• + c: S의 가장 뒤에 문자 c를 추가한다. 이때, c는 알파벳 소문자이다.
• -: S의 가장 앞에 있는 글자를 제거한다.

각각의 쿼리를 수행한 직후의 문자열 S의 길이는 항상 양수이다.

각 쿼리를 수행할 때마다 S의 서로 다른 부분 문자열의 개수를 구해야 한다.

입력

첫째 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 1,000,000)

둘째 줄부터 Q개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

출력

각각의 쿼리를 수행하고 난 뒤에 문자열 S의 서로 다른 부분 문자열의 개수를 모두 합한 값을 1,000,000,007로 나눈 나머지를 출력한다.

제한

힌트

• 첫 번째 쿼리를 수행하고 난 뒤에 S = a이다. 서로 다른 부분 문자열의 개수는 1개 (a)이다.
• 두 번째 쿼리를 수행하고 난 뒤에 S = ab이다. 서로 다른 부분 문자열의 개수는 3개 (a, b, ab)이다.
• 세 번째 쿼리를 수행하고 난 뒤에 S = aba이다. 서로 다른 부분 문자열의 개수는 5개 (a, b, ab, ba, aba)이다.
• 네 번째 쿼리를 수행하고 난 뒤에 S = abaa이다. 서로 다른 부분 문자열의 개수는 8개 (a, b, ab, ba, aa, aba, baa, abaa)이다.
• 다섯 번째 쿼리를 수행하고 난 뒤에 S = baa이다. 서로 다른 부분 문자열의 개수는 5개 (a, b, ba, aa, baa)이다.
• 여섯 번째 쿼리를 수행하고 난 뒤에 S = aa이다. 서로 다른 부분 문자열의 개수는 2개 (a, aa)이다.
• 일곱 번째 쿼리를 수행하고 난 뒤에 S = a이다. 서로 다른 부분 문자열의 개수는 1개 (a)이다.
• 여덟 번째 쿼리를 수행하고 난 뒤에 S = aa이다. 서로 다른 부분 문자열의 개수는 2개 (a, aa)이다.

정답은 1 +たす 3 +たす 5 +たす 8 +たす 5 +たす 2 +たす 1 +たす 2 =わ 27, 27 mod 1000000007 = 27 이다.