题目背景

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

题目描述

小宋有一个序列 $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$		$/$
$2,3$	$10^3$		$\mathbf{A}$
$4$			$\mathbf{B}$
$5\sim10$	$2\times 10^5$		$/$
$11\sim13$			$\mathbf{A}$
$14,15$			$/$
$16\sim18$	$5\times 10^5$		$\mathbf{B}$
$19\sim25$			$/$

特殊性质 $\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]$。