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 $w_i$.

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 $\sum_{i=1}^n \sum_{j=1}^n f(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)=w_iw_j$, otherwise $f(i,j)=0$. The number can be large, so print the number modulo $10^9+7$

Input

There are multiple test cases.

For each test case, the first line contains two numbers $n,m(1\leq n,m\leq 10^5)$.

There are $n$ numbers in the next line, the $i$-th means $w_i(0\leq w_i\leq 10^9)$.

Next $n-1$ lines contain two numbers each, $u_i$ and $v_i$, that means that there is an edge between $u_i$ and $v_i$.

The following are $m$ lines. Each line indicates an operation, and the format is "$1~u~w$"(modification) or "$2~u~v$"(query)$(0\leq w\leq 10^9)$

Output

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

Author

xudyh