题目描述

有一条长度为 $n$ 的链（ $\forall 1 \leq i < n$ ，点 $i$ 与点 $i+1$ 之间有一条边的无向图）， 每个点有一个整数权值，第 $i$ 个点的权值是 $a_i$ 。现在有 $m$ 个操作，每个操作如下：

操作 1（修改）：给定链上两个节点 $u$、$v$ 和一个整数 $d$，表示将链上 $u$ 到 $v$ 唯一的简单路径上每个点权值都加上 $d$。

操作 2（询问）：给定两个正整数 $l$、$r$，表示求链上所有节点个数大于等于 $l$ 且小于等于 $r$ 的简单路径节点权值和之和。由于答案很大，只用输出对质数 $1000000007$ 取模的结果即可。

一条节点个数为 $k$ 的简单路径节点权值和为这条上所有 $k$ 个节点（包括端点）的权值之和，而本题中要求是对所有满足要求的简单路径，求这一权值和的和。

由于是无向图，路径也是无向的，即点 $1$ 到点 $2$ 的路径与点 $2$ 到点 $1$ 的路径是同一条，不要重复计算。

输入格式

输入第一行包含两个正整数 $n$、$m$，分别表示节点个数和操作次数。

第二行包含 $n$个整数，其中第 $i$ 个数 $a_i$ 为第 $i$ 个点的初始权值。

接下来 $m$行，每行为 1 u v d或 2 l r的形式，分别表示进行一次操作 1（修改）或操作 2（询问）。

输出格式

对于每次询问，输出一行一个整数，表示答案对 $1000000007$ 取模的余数。

样例

input

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

output

5
13
9

节点个数为 $5$ 的简单路径只有 $1$ 条，权值和为 $5$，故第一次询问输出 $5$。

节点个数为 $1$ 的简单路径有 $5$ 条，每条权值和都是 $1$；节点个数为 $2$ 的简单路径有 $4$ 条，每条权值和都是 $2$，故第二次询问输出 $13 $。

在将点 $1$ 和点 $2$ 的权值加 $2$ 后，$5$条节点个数为 $1$ 的简单路径权值和分别 为 $3$、$3$、$1$、$1$、$1$，故第三次询问输出 $9$。

数据范围与提示

记操作 1（修改）的次数为 $m^\prime$。

对于全部数据， 保证 $n \leq 200000, m \leq 500000, m^\prime \leq 100000, 0 \leq a_i < 1000000007$

$1 \leq u \leq n, 1\leq v \leq n, 0 \leq d < 1000000007, l \leq r \leq n$ 。

对于每个数据点的详细规模与约定见下表。