题目背景

就算自身将浸于无边无际的悲叹

也要回归空白 空白的未来……

题目描述

泠珞有一个有 $n$ 个节点的无根树，第 $i$ 条边连接了第 $x_i$ 个节点和第 $y_i$ 个节点，第 $i$ 个节点上有一个正整数 $p_i$。

有时树上的数会发生变化，第 $k$ 条边两端的节点上的数字会发生交换，即 $p_{x_k}$ 会与 $p_{y_k}$ 互换。

有时泠珞会问你，如果一开始只有从节点 $s$ 到节点 $t$ 的简单路径上的节点是白色的，其他节点是蓝色的，执行下面的步骤直到所有节点都变成白色，执行步骤次数的期望是多少？

随机选择一个蓝色节点 $b$ 和一个白色节点 $w$，选择每个节点的概率与节点上的数字成正比，把节点 $b$ 到节点 $w$ 的简单路径上的所有节点涂为白色。

具体的，如果第 $i$ 个节点是白色的，选择他的概率是

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

如果第 $i$ 个节点是蓝色的，选择他的概率是

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

其中 $c_i$ 代表第 $i$ 个节点的颜色，为 $0$ 表示白色，为 $1$ 表示蓝色。

因为出题人的刻意设计，你要告诉泠珞答案 $\text{}\bmod10^9+7$ 的结果。

你能正确地回答泠珞的每一个问题吗？

输入格式

第一行包含两个正整数 $n,m$，表示树的结点数和操作总数。

第二行包含 $n$ 个正整数，第 $i$ 个正整数为 $p_i$，表示树上第 $i$ 个节点上的数字。

接下来的 $n-1$ 行，第 $i$ 行包含两个正整数 $x_i,y_i$，描述了树上的一条边 $(x_i,y_i)$。

接下来 $m$ 行每行表示一次修改或询问。首先读入一个正整数 $tp$ 表示指令类型：

• 若 $tp = 1$，接下来一个正整数 $k$ 表示交换第 $k$ 条边两端的节点上的数字 $p_{x_k}$ 与 $p_{y_k}$。
• 若 $tp = 2$，接下来两个正整数 $s,t$ 表示泠珞的一次询问。

输出格式

对于每次询问，输出一行一个整数，表示答案。

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

提示

【样例解释】

样例中后三个询问的答案写成分数形式分别是 $\frac{299}{132}$、$\frac{7}{5}$ 和 $\frac{21}{10}$。

【数据范围】

本题采用捆绑测试。

$\text{Subtask}$	$n,m\le$	特殊性质	分数
$1$	$12$	无	$10$
$2$	$2000$		$20$
$3$	$10^5$	$\forall1\le i\le n$，$p_i=114$	$10$
$4$		保证询问中 $s=1$
$5$		无	$25$
$6$	$5\times10^5$

对于所有数据，保证：$1\le n,m\le5\times10^5$，$1\le x_i,y_i\le n$，输入的图是一棵树，$1\le p_i\le10^9$，$\sum p_i<10^9+7$，$1\le tp \le2$，询问中 $1\le s,t\le n$，修改中 $1\le k\le n-1$。

【提示】

请注意常数因子对程序效率的影响。