[Bjoi2018]链上二次求和

内存限制：512 MiB 时间限制：140 Sec

有一条长度为n的链（1≤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个整数，其中第ii个数ai为第ii个点的初始权值。

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

记操作 1（修改）的次数为 m

n <= 200000,

m <= 500000,

m'<= 100000,

0 <= a_i <1000000007

1 <= u <= n

1<= v <= n

0 <= d < 1000000007

l <= r <= n

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

#5291. [Bjoi2018]链上二次求和