Strings

Interview

Time limit2sMemory limit512 MB

Summary

Build strings by concatenating earlier strings or slicing a substring, then output the sum of ASCII codes of the final string modulo 1e9+7, without materializing the possibly huge string.

Level: Medium5 of 10
Topics: Dynamic programming, String, Prefix sum, Implementation
Solved: No attempts yet

Problem

Gustave is an artist. His last project is to wrap the Eiffel Tower with a very long strip of fabric on which messages from people all over the world are written. Obviously, the strip has to be very, very long, and Gustave came up with the following way of building it. He starts with a single string on which all the messages are written. Then he repeatedly builds other strings, either by concatenating copies of two strings, or by making a copy of a section of consecutive characters from another string.

Once Gustave is happy with the final string he gets, he contacts a company to have the string printed on a strip of fabric. Being meticulous, Gustave does not want the company to make a single mistake. He thus computes a checksum out of his string and has the company do the same computation as a verification.

Input

The input consists of the following lines:

The first line contains an integer N.
The next line contains a string S(0) of lowercase alphabetic characters between ‘a’ and ‘z’.
The next N − 1 lines contain instructions to build strings S(1), ..., S(N − 1). The instruction to build string S(i) is either:
- “SUB x lo hi” with x, lo, hi integers such that 0 6 x < i and 0 6 lo 6 hi 6 length(S(x)), or
- “APP x y” with x, y integers such that 0 6 x, y < i.

Instruction “SUB x lo hi” means that S(i) is formed using (a copy of) characters of S(x) from index lo (inclusive) to hi (exclusive). Characters are numbered starting from 0. Instruction “APP x y” means that S(i) is formed by concatenating copies of strings S(x) and S(y) in that order, i.e., with S(x) coming first then S(y).

Output

The output should consist of a single line, whose content is an integer, the sum of all ASCII codes of the characters of the final string S(N − 1), modulo 1 000 000 007.

Constraints

1 ≤ N ≤ 2 500;
1 ≤ length(S(0)) ≤ 1 000;
the length of any string S(i) will never exceed 263 − 1.

Examples1

Example 1
Input
```
3
foobar
SUB 0 0 3
APP 1 1
```
Expected output
```
648
```