Gustave 是一位艺术家。他的最后一个项目是用一条非常长的织物带包裹埃菲尔铁塔，带子上写满了来自世界各地人们的留言。显然，这条带子必须非常非常长，Gustave 想出了以下构建方法：他首先从一个写有所有留言的字符串开始，然后通过连接两个字符串的副本，或者从另一个字符串中复制一段连续的字符，来反复构建其他字符串。

一旦 Gustave 对他得到的最终字符串感到满意，他就会联系一家公司将该字符串印在织物带上。由于一丝不苟，Gustave 不希望公司出现任何差错。因此，他计算了字符串的校验和，并让公司进行同样的计算以进行验证。

输入格式

输入包含以下行：

• 第一行包含一个整数 $N$。
• 下一行包含一个由 'a' 到 'z' 之间的小写字母组成的字符串 $S(0)$。
• 接下来的 $N - 1$ 行包含构建字符串 $S(1), \dots, S(N - 1)$ 的指令。构建字符串 $S(i)$ 的指令为以下两种之一：
  • “SUB x lo hi”，其中 $x, lo, hi$ 为整数，满足 $0 \leqslant x < i$ 且 $0 \leqslant lo \leqslant hi \leqslant \text{length}(S(x))$；
  • “APP x y”，其中 $x, y$ 为整数，满足 $0 \leqslant 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)$。

数据范围

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

输出格式

输出应包含一行，内容为一个整数，即最终字符串 $S(N - 1)$ 中所有字符的 ASCII 码之和，对 $1\,000\,000\,007$ 取模。

样例

输入格式 1

3
foobar
SUB 0 0 3
APP 1 1

输出格式 1

648