Problem Description
Rhason Cheung had a naive problem, and asked Teacher Mai for help. But Teacher Mai thought this problem was too simple, sometimes naive. So she ask you for help.
She has a tree with n vertices, numbered from 1 to n. The weight of i-th node is wi.
You need to support two kinds of operations: modification and query.
For a modification operation u,w, you need to change the weight of u-th node into w.
For a query operation u,v, you should output ∑ni=1∑nj=1f(i,j). If there is a vertex on the path from u to v and the path from i to j in the tree, f(i,j)=wiwj, otherwise f(i,j)=0. The number can be large, so print the number modulo 109+7
Input
There are multiple test cases.
For each test case, the first line contains two numbers n,m(1≤n,m≤105).
There are n numbers in the next line, the i-th means wi(0≤wi≤109).
Next n−1 lines contain two numbers each, ui and vi, that means that there is an edge between ui and vi.
The following are m lines. Each line indicates an operation, and the format is "1 u w"(modification) or "2 u v"(query)(0≤w≤109)
Output
For each test case, print the answer for each query operation.
Sample Input
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
Sample Output
341
348
612
