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

Source:

Submit