Description

以下描述不遵守任何化学规律。
化学反应中经常涉及到旧键的断裂与新键的生成，例如\(Coffee==CO+2Fe\)。
有一种化合物由\(n\)个原子构成, \(n\)个原子通过\(n-1\)个化学键连接成树形结构，其中第\(i\)个原子的能量为\(a_i\)。当一个原子处于活化状态时，该原子彻底消失，并且与它相连的所有化学键都将断裂。现在对化合物进行加热，每个原子未被活化的概率都为\(p/q\)，当若干原子被活化后，这颗树会断裂成一些联通块，定义每个联通块的爆发值为该联通块中所有原子的能量和的\(k\)次方。求断裂形成的所有联通块的爆发值的和的期望。你只需要求出期望对\(10^9+7\)取模的结果。

Format

Input

第一行有\(4\)个整数\(n, k, p, q\)。
第二行有\(n\)个整数\(a_i\)。
接下来有\(n-1\)行，每行有两个整数\(u, v\)，表示\(u\)与\(v\)之间通过化学单键连接。

Output

一行一个整数表示答案。

Sample 1

Input

3 2 1 2
1 2 4
1 2
1 3

Output

500000019

Limitation

1s, 512MiB for each test case.

Hint

\(a/b\)在模质数\(m\)意义下的值为\(a \times b^{m-2}\)。
例如， \(31/2\)在模\(1000000007\)意义下的值为\(31 \times 2^{1000000005}≡500000019(mod10^9+7)\)。

样例解释

当没有原子被活化时，概率为\(1/8\)，爆发值为\((1+2+4)^2 =49\)。
当\(1\)号原子被活化时，概率为\(1/8\)，爆发值为\(2^2+4^2=20\)。
当\(2\)号原子被活化时，概率为\(1/8\)，爆发值为\((1+4)^2 =25\)。
当\(3\)号原子被活化时，概率为\(1/8\)，爆发值为\((1+2)^2 =9\)。
当\(1, 2\)号原子被活化时，概率为\(1/8\)，爆发值为\(4^2 =16\)。
当\(1, 3\)号原子被活化时，概率为\(1/8\)，爆发值为\(2^2 =4\)。
当\(2, 3\)号原子被活化时，概率为\(1/8\)，爆发值为\(1^2 =1\)。
当\(1, 2, 3\)号原子被活化时，概率为\(1/8\)，爆发值为\(0\)。
期望为\(124/8=31/2\)，即\(500000019\)。

数据规模与约定

对于所有数据， \(n ≤ 2×10^5, 2 ≤ k ≤ 10, 0 ≤ p < q ≤ 10^3, 0 ≤ a_i ≤ 10^3\)。

Source

CSP2019模拟试题五