Once again, Su was caught sleeping in an algorithms class. This was the Yth time (The teacher lost track of Y). The teacher is very angry and decided to punish him and gave an extra assignment.

The assignment is as follows:

You are given a tree having N nodes rooted at 1. Each node is numbered from 1 to N. Each node contains a number $X_i$ $\forall$ $i \in [1, N]$. You have to perform Q operations which are one among the 3 types mentioned below

• 1 V $\alpha$ $\beta$ - Let T denote the subtree rooted at V. Perform the below operation: $X_i = \alpha * X_i + \beta \ \forall i \in T$
• 2 V - Let T denote the subtree rooted at V. Find the value of the below expression. $(\sum_{i \in T}\sum_{j \in T}\sum_{k \in T}\sum_{l \in T} (X_i + X_j + X_k + X_l)^2) \ \ \% \ \ M$
• 3 V - Let T denote the subtree rooted at V. Find the value of the below expression. $(\sum_{i \in T}\sum_{j \in T}\sum_{k \in T}\sum_{l \in T} (X_i + X_j + X_k + X_l)^3) \ \ \% \ \ M$

Input format

The first line contains two space separated integers N and Q.
Next line contains N space separated integers, $i_{th}$ of them is value $X_i$.
Then follows $N - 1$ lines, each containing two space separated integers A and B, denoting an undirected edge between nodes A and B.
Then follows Q lines, each line describing a query as given in the problem statement.

Output format

For each query of type 2 and type 3, print a single line containing the answer.

Constraints

$1 \leq N \leq 5 * 10^5$
$1 \leq Q \leq 2 * 10^5$
$1 \leq X[i] \leq 10^8$
$1 \leq \alpha, \beta \leq 10^4$
$1 \leq V, A, B \leq N$
$A \neq B$
$M = 1000000007$
The given graph denotes an undirected tree rooted at 1.

Note : This problem has binary scoring. You will receive points only if you pass all test files successfully.