Under construction

Still being built. Things may change

KDH, Son of the Typhoon

Time limit2sMemory limit512 MB

Summary
On a tree where every pair of vertices adds 1 traffic to each path edge, vertices survive independently with probability p; find the expected total traffic.
Level

Medium7 of 10

Topics
Tree, DFS, Probability, Combinatorics
Solved
No attempts yet

Problem

KDH, the son of the typhoon (the stage name is read as kkeu-deu-heu) will hold a concert at the Suwon Sports Complex near his school. The nickname says it plainly: his popularity stirs up a typhoon wherever he goes. This time the typhoon is about to sweep through Songjuk-dong.

Songjuk-dong is a single tree of NN points joined by N−1N-1 roads. Gyeonggi Science High School, the KT wiz ballpark, Homeplus, Bulloman, Sulbing and every other place there are all connected to one another. Songjuk-dong is a busy neighborhood, so for each pair {u,v}\{u, v\} of two different points, every road on the path between them gains 11 unit of traffic. The order inside a pair does not matter.

When the typhoon sweeps through Songjuk-dong, each point collapses with probability pp, independently of the others. If even one point on a path collapses, counting both endpoints, that path adds no traffic at all.

Less traffic means less concert revenue. Compute the expected value of the total traffic of every road in Songjuk-dong after the typhoon.

Input

The first line contains the number of points NN (1≤N≤200 0001 \le N \le 200\,000) and two integers aa and bb that describe the probability p=abp = \frac{a}{b}. (1≤a≤b≤1091 \le a \le b \le 10^9)

Each of the next N−1N-1 lines contains the two points uiu_i and viv_i that a road joins. (1≤ui,vi≤N1 \le u_i, v_i \le N, ui≠viu_i \ne v_i)

The given graph is always a connected tree.

Output

On the first line, print the expected value of the total traffic of every road in Songjuk-dong after the typhoon.

Write that expected value as a fraction xy\frac{x}{y} in lowest terms and print x×y−1 mod (109+7)x \times y^{-1} \bmod (10^9+7), where y−1y^{-1} is the modular inverse of yy modulo 109+710^9+7.

Hint

The expected value in the first example is 198\frac{19}{8}.

Examples2

  1. Example 1

    Input
    5 1 2
    1 2
    1 3
    2 4
    2 5
    
    Expected output
    375000005
    
  2. Example 2

    Input
    1 1 2
    
    Expected output
    0