시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

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

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

각 쿼리를 수행한 후에 S의 서로 다른 부분 문자열의 개수를 출력하는 프로그램을 작성하시오. 

입력

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

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

출력

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

예제 입력 1

8
+ a
+ b
+ a
+ a
-
-
-
+ a

예제 출력 1

27

힌트

  • 첫 번째 쿼리를 수행하고 난 뒤에 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 이다.

출처