树上路径平方和

题目描述

Y 同学拥有一棵包含 $N$ 个节点的树，节点编号从 $1$ 至 $N$。初始时，每个节点 $i$ 上都有一个整数权值 $A_i$。

为了深入研究树上结构的代数性质，Y 同学需要对这棵树执行 $M$ 次操作。操作共分为以下两种类型：

• 1 u v x：将节点 $u$ 到节点 $v$ 的简单路径上所有节点的权值均加上 $x$。
• 2 u v：查询节点 $u$ 到节点 $v$ 的简单路径上所有节点权值的平方和。

具体而言，若路径上的节点集合为 $S$，则类型 $2$ 操作需要计算：

Y 同学希望你能编写一个程序，帮助他快速处理这些操作。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示树的节点数和操作次数。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示各节点的初始权值。 接下来的 $N-1$ 行，每行包含两个正整数 $u, v$，表示节点 $u$ 与节点 $v$ 之间存在一条边。 接下来的 $M$ 行，每行描述一个操作。格式为 1 u v x 或 2 u v。

输出格式

对于每个类型 $2$ 的查询，输出一行一个整数，表示该路径上节点权值的平方和对 $10^9 + 7$ 取模后的结果。

样例

样例输入 #1

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

样例输出 #1

26
74
54

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N, M \le 10^5$，$0 \le A_i, x \le 10^9$，$1 \le u, v \le N$。

特殊性质 A：保证给定的树是一条链，即第 $i$ 条边连接节点 $i$ 与 $i+1$。 特殊性质 B：保证所有的操作均为类型 $2$ 操作（即不存在修改操作）。