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$
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)$
For each test case, print the answer for each query operation.