#215362. [SWERC 2018] Strings

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 from 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 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.

The input consists of the following lines:

• The first line contains an integer .
• The next line contains a string of lowercase alphabetic characters between ‘a’ and ‘z’.
• The next lines contain instructions to build strings . The instruction to build string is either:
  • “SUB x lo hi” with integers such that and , or
  • “APP x y” with integers such that .

Instruction “SUB x lo hi” means that is formed using (a copy of) characters of from index (inclusive) to (exclusive). Characters are numbered starting from 0.

Instruction “APP x y” means that is formed by concatenating copies of strings and in that order, i.e., with coming first then .

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 , modulo .

样例输入 1

3
foobar
SUB 0 0 3
APP 1 1

样例输出 1

648

Limits

• ;
• ;
• the length of any string will never exceed .