说明

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 \leq x < i$ 且 $0 \leq lo \leq hi \leq \text{length}(S(x))$，或者
  • “APP x y”，其中 $x, y$ 是整数，满足 $0 \leq x, y < i$。

指令 “SUB x lo hi” 表示 $S(i)$ 由 $S(x)$ 中从索引 $lo$（包含）到 $hi$（不包含）的字符（的一个副本）构成。字符编号从 0 开始。

指令 “APP x y” 表示 $S(i)$ 通过按顺序连接字符串 $S(x)$ 和 $S(y)$ 的副本来构成，即 $S(x)$ 在前，$S(y)$ 在后。

输出格式

输出应包含一行，内容为一个整数，表示最终字符串 $S(N-1)$ 的所有字符的 ASCII 码之和，对 $1000000007$ 取模的结果。

3
foobar
SUB 0 0 3
APP 1 1

648

提示

数据范围

• $1 \leq N \leq 2500$；
• $1 \leq \text{length}(S(0)) \leq 1000$；
• 任何字符串 $S(i)$ 的长度永远不会超过 $2^{63} - 1$。

翻译由 DeepSeek 完成