Rhason Cheung 有一个朴素的问题，并向 Teacher Mai 求助。但 Teacher Mai 认为这个问题太简单了，有时甚至有些幼稚。所以她让你来帮忙。

她有一棵包含 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。第 $i$ 个节点的权重为 $w_i$。

你需要支持两种操作：修改和查询。

对于修改操作 $u, w$，你需要将第 $u$ 个节点的权重修改为 $w$。

对于查询操作 $u, v$，你需要输出 $\sum_{i=1}^{n} \sum_{j=1}^{n} f(i, j)$。如果树上从 $u$ 到 $v$ 的路径与从 $i$ 到 $j$ 的路径有公共顶点，则 $f(i, j) = w_i w_j$，否则 $f(i, j) = 0$。由于结果可能很大，请将其对 $10^9 + 7$ 取模后输出。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)。

接下来一行包含 $n$ 个整数，其中第 $i$ 个数表示 $w_i$ ($0 \le w_i \le 10^9$)。

接下来的 $n-1$ 行，每行包含两个数字 $u_i$ 和 $v_i$，表示 $u_i$ 和 $v_i$ 之间有一条边。

随后有 $m$ 行。每行表示一个操作，格式为 “1 u w” 表示修改，或 “2 u v” 表示查询 ($0 \le w \le 10^9$)。

输出格式

对于每个测试用例，输出每个查询操作的答案。

样例

输入 1

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

输出 1

341
348
612