暂无测试数据。

题目描述

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

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

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

假如本次作业的答案是\(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

样例解释

操作序号	操作	小明的答案	helloworld的子串
\(0\)（初始时）	无	\(\varnothing\)	无
\(1\)	1 h	h	h
\(2\)	1 w	hw	h和w
\(3\)	1 x	hwx	h和w
\(4\)	1 l	hwxl	h、w和l
\(5\)	2 2 3 el	hell	所有hell的非空子串

数据范围

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

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

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

其中\(|a|\)表示\(a\)的长度。