407581: GYM102832 I Kawaii Courier

I. Kawaii Couriertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Once there was a courier named Kujou Kawaii, whose work was to collect packages from people around the city. The city consisted of $$$n$$$ communities, numbered from $$$1$$$ to $$$n$$$, together with $$$n - 1$$$ bidirectional roads connecting them. The express distribution center of this city was located at the community numbered $$$k$$$. Of course, any two communities were guaranteed to be connected by these roads. Kujou's electromobile was so small that she could only carry packages from $$$1$$$ community at the same time. She would always first deliver packages from the community numbered $$$1$$$, then those from the one numbered $$$2$$$, etc., and finally the packages from the one numbered $$$n$$$.

Let's calculate Kujou's tiredness index after a whole day of work! We only consider the trip from each community to the express distribution center. Unfortunately, Kujou had no sense of direction. On arriving at a community, she would uniformly randomly choose a road (including the one she came from) to follow, until she finally reached the community where the express distribution center was located. Suppose the trip from the community numbered $$$i$$$ to the express center passed $$$d_i$$$ roads. Kujou's tiredness was influenced by three factors.

1. Tiredness $$$a_i$$$ from beginning of the work. $$$a_i$$$ equals $$$i$$$.
2. Physical tiredness $$$b_i$$$ during the current delivery. $$$b_i$$$ equals $$$d_i$$$.
3. Emotional tiredness $$$c_i$$$. Kujor enjoyed traveling all over the city, so $$$c$$$ was initialized to $$$1$$$ for each delivery, and was multiplied by $$$x$$$ where $$$x$$$ is a rational number in $$$(0, 1]$$$ for each road Kujor passes. In other words, $$$c_i$$$ equals $$$x^{d_i}$$$.

For each delivery $$$i$$$, Kujou's final tiredness index would be $$$m_i = a_i \times b_i \times c_i$$$, and you need to calculate the expected tiredness index for each delivery.

It can be shown that $$$m_i$$$ can be expressed as an irreducible fraction $$$\frac{p_i}{q_i}$$$, where $$$p_i$$$ and $$$q_i$$$ are integers. It is then guaranteed in all test cases that $$$q_i \not\equiv 0 \pmod{10^9+7}$$$. In this case, $$$m_i$$$ modulo $$$10^9 + 7$$$ is well-defined, which is some integer $$$m'_i$$$ such that $$$m'_i q_i \equiv p_i \pmod{10^9 + 7}$$$. Furthermore, you only need to output $$$m'_1 \oplus \dots \oplus m'_n$$$ to prevent large output, where $$$\oplus$$$ denotes the bitwise XOR operation.

Input

The first line contains four integers $$$n$$$, $$$k$$$, $$$p_x$$$ and $$$q_x$$$ ($$$2 \leq n \leq 10^5, 1 \leq k \leq n, 1 \leq p_x \leq q_x \leq 10^7$$$), where $$$x$$$ is given in the form $$$p_x / q_x$$$.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), indicating that there was a road connecting the community numbered $$$u$$$ and the one numbered $$$v$$$. It is guaranteed that all communities are connected by these $$$n - 1$$$ roads.

Output

Print $$$m'_1 \oplus \dots \oplus m'_n$$$.

ExamplesInput

3 1 1 1
1 2
3 1

Output

1

Input

3 1 1 2
1 2
2 3

Output

695000161

Input

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

Output

1000005122

Note

In the second example, $$$m_1 = 0$$$, $$$m_2 = \frac{36}{49}$$$, $$$m_3 = \frac{48}{49}$$$.