[KMOI R1] 五五五五（Hard）

“事类相推，各有攸归，故枝条虽分而同本干知，发其一端而已。又所析理以辞，解体用图，庶亦约而能周，通而不黩，览之者思过半矣。”——刘徽

小宋有一个序列 $A=\{a_1,a_2\dots,a_n\}$，其中 $\forall i\in [1,n],a_i\in[0,9]$。 对于 $1\le l\le r\le n$，他记 $f(l,r)$ 等于 $\overline{a_la_{(l+1)}\dots a_r}$ 的末尾连续 $5$ 的个数。 例如：对于序列 $a=\{1,1,4,5,1,4\}$，$f(2,4)=1,f(1,3)=0$。 不过小宋会对这个序列不断地操作，具体地，他会做以下操作： - $(1,x,y)$：将第 $x$ 个数改为 $y$（$x\in[1,n],y\in[0,9]$）。 - $2$: 将序列 $a$ 反转，例如 $\{1,1,4,5\}$ 反转之后就是 $\{5,4,1,1\}$。 - $3$：对序列进行询问。 - $(4,l,r)$：对序列进行询问。 对于每一种操作 $3$，请你输出: $$\Big(\sum\limits_{l=1}^ {n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$ 对于每一个操作 $4$，请你输出： $$\Big(\sum\limits_{i=l}^{r}a_i\Big) \bmod 10^9+7$$

第一行两个正整数 $n,q$，表示序列的数个数和询问的个数。 第二行 $n$ 个整数 $a_1, a_2,\dots a_n$，表示序列 $A$。 接下来 $q$ 行，每行一个或三个正整数，表示一次操作。

对于每一次操作 $3$ 和操作 $4$，输出答案。

3 4
1 5 5
1 3 3
3
1 1 5
4 1 3

2
13

6 5
1 1 4 5 1 4
3
2
3
1 1 5
4 1 4

4
3
15

## 样例 $1$ 解释： | 操作 | 操作后的序列 | 答案 | | :----------: | :----------: | :----------: | | $(1,3,3)$ | $\{1,5,3\}$ | $/$ | | $3$ | $/$ | $2$ | | $(1,1,5)$ | $\{5,5,3\}$ | $/$ | | $(4,1,3)$ | $/$ | $13$ | ## 样例 $2$ 解释： | 操作 | 操作后的序列 | 答案 | | :----------: | :----------: | :----------: | | $3$ | $/$ | $4$ | | $2$ | $\{4,1,5,4,1,1\}$ | $/$ | | $3$ | $/$ | $3$ | | $(1,1,5)$ | $\{5,1,5,4,1,1\}$ | $/$ | |$(4,1,4)$|$/$|$15$| ## 数据范围 | 测试点编号 | $n\le$ |$q\le$| 特殊性质 | | :----------: | :----------: | :----------: | :----------: | |$1$|$100$|$100$|$/$| |$2,3$|$10^3$|$10^3$|$\mathbf{A}$| |$4$|$10^3$|$10^3$|$\mathbf{B}$| |$5\sim10$|$2\times 10^5$|$2\times 10^5$|$/$| |$11\sim13$|$2\times 10^5$|$2\times 10^5$|$\mathbf{A}$| |$14,15$|$2\times 10^5$|$2\times 10^5$|$/$| |$16\sim18$|$5\times 10^5$|$5\times 10^5$|$\mathbf{B}$| |$19\sim25$|$5\times 10^5$|$5\times 10^5$|$/$| 特殊性质 $\mathbf{A}:$ 没有操作 $2$。 特殊性质 $\mathbf{B}:$ 没有操作 $3$。 对于 $100\%$ 的数据：$1\le n\le 5\times 10^5$，$1\le q\le 5\times 10^5$。 $\forall i\in [1,n]$，满足 $a_i\in[0,9]$。