Sometimes Naive

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

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)

For each test case, print the answer for each query operation.

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

341
348
612

2015 Multi-University Training Contest 9