线段树打标记2

题目描述

给$n$个数$a_1, a_2, a_3, \dots, a_n$。

支持$q$个操作：

1. 1 l r d，令所有的$a_i (l\leq i\leq r)$加上$d$。
2. 2 l r d，令所有的$a_i (l\leq i\leq r)$乘上$d$。
3. 3 l r d，令所有的$a_i (l\leq i\leq r)$等于$d$。
4. 4 l r，查询$\left(\sum_{i=l}^r a_i\right) \bmod (10^9+7)$。

输入格式

第一行两个整数$n, q (1\leq n, q\leq 2 \times 10^5)$。

接下来一行$n$个整数$a_1, a_2, \dots, a_n (1 \leq a_i\leq 10^9)$。

接下来$q$行，每行一个形如1 l r d, 2 l r d, 3 l r d或者4 l r的操作，保证$1\leq l\leq r\leq n, 1\leq d\leq 10^9$。

输出格式

对于每个查询，输出一行，表示答案。

样例输入

5 7
1 2 3 4 5
4 1 5
1 2 3 4
4 1 5
2 3 4 5
4 1 5
3 4 5 1
4 1 5

样例输出

15
23
67
44