문자열

Gustave는 예술가다. 그의 마지막 프로젝트는 에펠탑을 매우 긴 천 조각으로 감싸는 것이고, 그 천에는 전 세계 사람들의 메시지가 적혀 있다. 당연히 천은 아주아주 길어야 하며, Gustave는 다음과 같은 방법으로 천을 만들기로 했다. 먼저 모든 메시지가 적힌 문자열 하나로 시작한다. 그다음 두 문자열의 복사본을 이어 붙이거나, 다른 문자열에서 연속한 문자 구간을 복사하는 방식으로 계속해서 다른 문자열을 만든다.

Gustave가 최종 문자열에 만족하면, 그는 회사에 연락해 그 문자열을 천 조각에 인쇄하도록 한다. 꼼꼼한 성격인 Gustave는 회사가 단 하나의 실수도 하지 않기를 바란다. 그래서 그는 자신의 문자열로 체크섬을 계산하고, 회사에도 같은 계산을 하도록 해 검증한다.

입력은 다음 줄들로 구성된다.

• 첫째 줄에 정수 N이 주어진다.

• 다음 줄에 ‘a’부터 ‘z’까지의 소문자 알파벳으로 이루어진 문자열 S(0)이 주어진다.

• 다음 N − 1개의 줄에는 문자열 S(1), ..., S(N − 1)을 만드는 지시가 주어진다. 문자열 S(i)를 만드는 지시는 다음 중 하나다.

  • “SUB x lo hi”: x, lo, hi는 0 6 x < i이고 0 6 lo 6 hi 6 length(S(x))인 정수다.
  • “APP x y”: x, y는 0 6 x, y < i인 정수다.

지시 “SUB x lo hi”는 S(i)가 S(x)의 lo번째 문자부터 hi번째 문자 바로 앞까지(lo는 포함, hi는 제외) 복사한 것으로 만들어진다는 뜻이다. 문자는 0부터 번호를 매긴다. 지시 “APP x y”는 S(i)가 문자열 S(x)와 S(y)의 복사본을 그 순서대로 이어 붙여, 즉 S(x)가 먼저 오고 S(y)가 그다음에 오도록 만들어짐을 뜻한다.

출력은 한 줄이며, 최종 문자열 S(N − 1)의 모든 문자의 ASCII 코드 합을 1 000 000 007로 나눈 나머지를 정수로 출력한다.

• 1 ≤ N ≤ 2 500;
• 1 ≤ length(S(0)) ≤ 1 000;
• 어떤 문자열 S(i)의 길이도 263 − 1을 넘지 않는다.