题目背景

或真亦或伪？飘如陌上尘。

题目描述

对于长度为 $n$ 的序列 $a$，有以下三种操作：

• 选定两个数 $1\le l\le r\le n$，使得 $a_{l\sim r}$ 减一，消耗一点代价。
• 选定一个数 $1\le k\le n$，使得 $a_{k\sim n}$ 减一，不消耗代价。
• 选定一个数 $1\le k\le n$，使得 $a_{1\sim k}$ 减一，不消耗代价。

需要通过若干次操作将 $a$ 的每个元素变为同一个非负整数 $p$，设消耗的总代价为 $m$。记 $f(a)$ 为所有可行方案中 $m-p$ 的最小值。

有一个长为 $n$ 的序列 $v$，有 $q$ 次操作，每次为其中之一：

1. 修改操作。给出三个数 $l,r,x$，将 $v_{l\sim r}$ 修改为 $x$。
2. 询问操作。给出两个数 $l,r$，询问所有长度为 $r-l+1$，满足 $0\le a_i\le v_{i+l-1}$ 的序列 $a$，其 $f(a)$ 的和。

输入格式

第一行输入两个数 $n,q$。

第二行输入 $n$ 个数，第 $i$ 个数表示 $v_i$。

接下来 $q$ 行，第一个数为 $op\in [1,2]$ 表示操作类型，若 $op=1$，接下来输入三个数 $l,r,x$，表示一次修改；否则输入两个数 $l,r$，表示一次询问。

输出格式

输出若干行，对应每次询问的答案，对 $10^9+7$ 取模。

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

1000000005
1000000002
2
5

提示

本题 I/O 量较大，请使用较快的 I/O 方式。

样例解释：

对于第一个询问，序列 $a$ 可以为 $\{0,0\},\{0,1\},\{0,2\},\{1,0\},\{1,1\},\{1,2\}$，$f(a)$ 分别为 $0,0,0,0,-1,-1$，和为 $-2$，在模 $10^9+7$ 意义下为 $1000000005$。

数据范围：

Subtask	分值	$n \le$	$q \le$	$v_i \le$	$x \le$	特殊性质
$1$	$20$	$10$	<	$3$	<	无
$2$	$15$	$200$		$500$		^
$3$	$5$	$2 \times 10^3$		$10^9$		A
$4$	$15$	^		^		无
$5$	$10$	$2\times 10^4$	<			B
$6$	$15$	$2 \times 10^5$				^
$7$	$20$	^				无

对于 $100\%$ 的数据，保证： $2\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$0\le v_i,x\le 10^9$，$1\le l<r \le n$，$opt\in[1,2]$。

特殊性质 A：数据中任意时刻 $v_i$ 单调不降。

特殊性质 B：数据中不包含修改操作。