暂无测试数据。

定义数列 $F$：

$F_0=0,F_1=1,F_n=p\times F_{n-1}+q\times F_{n-2}(n\geq 2)$

给定一棵 $n$ 个节点的树，每个点 $i$ 有一个权值为 $a_i$。

接下来有 $m$ 个操作：

1 u v：设树上 $u$ 点到 $v$ 点路径上节点为 $b_1,b_2,\cdots,b_k$，询问 $\sum\limits_{i=1}^k\sum\limits_{j=i}^kF(\sum\limits_{t=i}^ja_{b_t})$ 的值。由于答案可能很大，你需要对 $10^9+7$ 取模。

2 x y z：删除连接 $y$ 与 $x$ 的无向边（保证存在此边），然后加入一条连接 $y$ 与 $z$ 的无向边，保证操作后仍然为一棵树。

3 u v k：将 $u$ 到 $v$ 路径上所有节点的权值修改为 $k$。

输入格式

第 $1$ 行，$4$ 个正整数 $n, m, p, q$。

第 $2$ 行，$n$ 个正整数 $a_i$ 表示各点的点权。

接下来 $n-1$ 行，每行两个数 $x_i,y_i$，表示初始树上存在连接 $x_i$ 与 $y_i$ 的无向边。

最后 $m$ 行，每行一个操作。操作的格式请参考题面。

输出格式

对于每一个操作 $1$，输出一行表示答案。

数据范围

对于 $30\%$ 的数据，满足 $1\leq n,m \leq 500, 1\leq a_i, k, p, q\leq 10$。

对于 $100\%$ 的数据，满足 $1\leq n,m \leq 10^5, 1\leq a_i, k, p, q\leq 10^9$。

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

17
7
36