Background

Even if I myself will sink into boundless sorrow.

I still have to return to blank, to a blank future……

Problem Description

Lingluo has an unrooted tree with $n$ nodes. The $i$-th edge connects node $x_i$ and node $y_i$. Node $i$ has a positive integer $p_i$ on it.

Sometimes, the numbers on the tree will change. The numbers on the two endpoints of the $k$-th edge will be swapped, i.e., $p_{x_k}$ and $p_{y_k}$ will be exchanged.

Sometimes Lingluo will ask you: if at the beginning only the nodes on the simple path from node $s$ to node $t$ are white and all other nodes are blue, then if you repeatedly perform the following step until all nodes become white, what is the expected number of steps?

Randomly choose one blue node $b$ and one white node $w$. The probability of choosing each node is proportional to the number on that node. Then paint all nodes on the simple path from node $b$ to node $w$ to white.

Specifically, if node $i$ is white, the probability of choosing it is

$$\frac{p_i}{\sum\limits_{c_j=0}p_j}$$

If node $i$ is blue, the probability of choosing it is

$$\frac{p_i}{\sum\limits_{c_j=1}p_j}$$

where $c_i$ denotes the color of node $i$: $0$ means white, and $1$ means blue.

Due to the problem setter’s deliberate design, you need to output the result of the answer $\text{}\bmod10^9+7$.

Can you correctly answer every question from Lingluo?

Input Format

The first line contains two positive integers $n,m$, representing the number of nodes in the tree and the total number of operations.

The second line contains $n$ positive integers. The $i$-th integer is $p_i$, representing the number on node $i$.

The next $n-1$ lines describe the edges of the tree. Line $i$ contains two positive integers $x_i,y_i$, describing an edge $(x_i,y_i)$.

Then follow $m$ lines, each representing one modification or one query. First read a positive integer $tp$ indicating the operation type:

• If $tp = 1$, read a positive integer $k$, meaning to swap the numbers $p_{x_k}$ and $p_{y_k}$ on the two endpoints of the $k$-th edge.
• If $tp = 2$, read two positive integers $s,t$, meaning one query from Lingluo.

Output Format

For each query, output one line with one integer, representing the answer.

5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
2 1 5
2 3 3
1 1
2 4 5
2 1 3

2
719696977
800000007
700000007

Hint

Sample Explanation

In the sample, the answers to the last three queries, written as fractions, are $\frac{299}{132}$, $\frac{7}{5}$, and $\frac{21}{10}$.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that: $1\le n,m\le5\times10^5$, $1\le x_i,y_i\le n$, the input graph is a tree, $1\le p_i\le10^9$, $\sum p_i<10^9+7$, $1\le tp \le2$, in queries $1\le s,t\le n$, and in modifications $1\le k\le n-1$.

Note

Please pay attention to the impact of constant factors on program efficiency.

Translated by ChatGPT 5