시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 37 10 10 32.258%

문제

태풍의 아들 'KDH'(끄드흐라 읽는다)가 학교 근처에 있는 수원 종합운동장에서 콘서트를 열기로 했다. 그의 별명 '태풍의 아들'에서 알 수 있듯이, 그의 넘쳐나는 인기는 그가 가는 모든 곳마다 태풍을 불러일으킨다. 그리고, 이 태풍은 곧 송죽동을 휩쓸고 지나갈 것이다!

송죽동은 $N$개의 노드로 이루어진 하나의 연결된 트리 모양이다. 경기과학고등학교, KT wiz 야구장, 홈플러스, 불로만, 설빙 등 다양한 장소들이 $N-1$개의 길을 통해 모두 서로 연결되어 있다. 송죽동은 매우 번성한 곳이기 때문에 임의의 두 지점을 잇는 경로에 대해 그 경로상의 모든 도로에 1만큼의 교통량이 가산된다.

KDH가 몰고 온 태풍이 송죽동을 휩쓸고 지나가면, 송죽동의 각 지점은 $p$의 확률로 붕괴된다. 송죽동의 두 지점을 잇는 임의의 경로에 대해, 양 끝 점을 포함해서 경로 상에 있는 마을 중 하나라도 붕괴된다면 그 경로에 대해서는 교통량이 가산되지 않는다. 

태풍 때문에 교통량이 줄어들면, 콘서트 수익도 자연히 줄어들 것이다. 태풍 이후 송죽동 교통량의 기댓값을 정확히 알 수 있다면 손해를 미리 대비할 수 있을 것이다. KDH를 도와주자!

입력

첫 번째 줄에는 송죽동의 지점 수 $N$ ($1 \le N \le 200\, 000$) 과 확률 $p$를 나타내는 두 정수 $a$와 $b$가 주어진다. ($p= \frac{a}{b}$, $a$와 $b$는 각각 $1$ 이상 $10^9$ 이하)

다음 $N-1$줄에는 각 도로가 잇는 두 지점 $u_i$, $v_i$가 주어진다. ($1 \le u_i, v_i \le N$)

입력은 연결된 트리 형태임이 보장된다.

출력

첫 번째 줄에 태풍이 분 이후 송죽동에 있는 모든 도로의 교통량 기댓값의 합을 나타내는 수를 출력한다.

즉, 구한 기댓값을 $\frac{x}{y}$라 할 때, $x \times y^{-1}$ (mod $10^9+7$)의 값을 출력한다. (단, $y^{-1}$은 $y$의 $10^9+7$에 대한 모듈러 역원(modular inverse))

예제 입력

5 1 2
1 2
1 3
2 4
2 5

예제 출력

375000005

힌트

예제 출력은 $\frac{19}{8}$를 의미한다.