题目描述

给定长度为$n$的序列$a_i$，以及$m$个操作。

操作一：1 l r x，对于$\forall i\in [l,r]$，$a_i$乘上一个数$x$。 操作二：2 l r x，对于$\forall i\in [l,r]$，$a_i$加上一个数$x$。 操作三：3 l r，询问$\forall i\in [l,r]$，$a_i$的和。 对于每个操作三，给出你的答案。由于答案可能很大，输出在模$10^9+7$下的答案即可。

输入格式

第一行输入两个整数$n,m$。 第二行输入$n$个整数$a_i$。 接下来$m$行，每行输入一个操作，格式如题面所示。

输出格式

对于每个询问三，输出一行一个整数，表示你的答案。

样例输入 #1

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

样例输出 #1

86
82

说明/提示

保证$1\leq n,m\leq10^5,1\leq a_i,x\leq 10^9,1\leq l\leq r\leq n$。