暂无测试数据。

题目描述

不识庐山真面目，只缘 生 在此山中。——小明

鱿鱼晓鸣飞长洗唤输血搓鳖子（划掉）

由于小明非常喜欢书写错别字，他的作业本上到处都是划痕（就像这（殃）样和（内）那样）（括号代表划痕）。

假如本次作业的答案是$a$（均为小写字母），小明写作业的操作有：

• 1 c表示写了一个字母$c$。
• 2 l r s表示发现编号从$l$到$r$（从$1$开始）自己的答案不对，把它改为$s$。

每一次操作后，求小明的答案里有多少个是$a$的非空子串。

输入格式

第一行，$a,n$，其中$n$表示小明对自己的答案做了$n$次修改。

以下每一行一个操作。

输出格式

每一次操作后的答案取模于$10^9+7$的结果。

输入样例

helloworld 5
1 h
1 w
1 x
1 l
2 2 3 el

输出样例

1
2
2
3
10

样例解释

数据范围

对于$20\%$的数据，$|a|,n\leq250$。

对于$50\%$的数据，$|a|,n\leq1000$。

对于$100\%$的数据，$|a|,n\leq2\times10^5$。

其中$|a|$表示$a$的长度。