30161번 - 반사복제된 트리

문제

어떤 트리 $T$의 "반사복제" 행위를 다음과 같이 정의한다.

• $T$의 각 리프 노드에 대하여, 그 리프 노드에다가 원래 트리 $T$를 해당 리프 노드를 기준으로 동일한 위상으로 복제시킨다. 동일한 위상으로 복제시킨다는 것은, 어떤 리프 노드를 $L$ 이라고 하면 트리를 통째로 복제한 후 두 트리의 $L$에 해당하는 부분을 겹친다는 것을 의미한다.

이 그림은 주어진 트리(화살표 왼쪽)를 반사복제시켜서 만든 새로운 트리(화살표 오른쪽)이다. 굵은 원이 기존의 트리이며 얇은 원이 각 리프노드별로 동일한 위상으로 복제된 트리이다. 새로 생성된 노드는 기존의 노드와 구분하기 위해 번호에 쌍따옴표를 붙였다.

$N$개의 노드를 가진 어떤 트리가 주어지고, 이 트리를 $k$번 반사복제했을 때, 이 트리의 모든 노드 간 노드의 거리를 10ドル^{9} + 7$ 로 나눈 나머지를 구하시오. 이때, 모든 노드 간 노드의 거리를 수식으로 표현하면 다음과 같다. ($V$는 전체 노드의 집합, $dist$는 두 노드 사이의 거리(= 두 노드를 잇는 경로 상의 간선의 개수)를 의미한다.)

$$\frac{1}{2} \sum_{v_{1} \in V} \sum_{v_{2} \in V} dist(v_{1}, v_{2})$$

입력

첫 번째 줄에 트리에 있는 노드의 개수 $N$과 이 트리를 반사복제할 횟수 $K$가 공백으로 구분되어 주어진다. (2ドル \leq N \leq 100,000,ドル ,円 1ドル \leq K \leq 100,000$)

두 번째 줄부터 $N-1$개의 줄에 걸쳐 두 정수 $u_{1},ドル $u_{2}$가 공백으로 구분되어 주어진다. 이는 트리의 $u_{1}$번 노드와 $u_{2}$번 노드가 서로 연결되어 있음을 의미한다. (1ドル \leq u_{1} < u_{2} \leq N$) 간선들로 트리가 만들어지지 않는 입력은 주어지지 않는다.

출력

정답을 10ドル^{9} + 7$로 나눈 나머지를 출력한다.

제한

노트

첫 번째 예제는 입력으로 주어진 트리를 1ドル$번 반사복제한 트리에 관하여 묻고 있다. 이를 그림으로 그리면 다음과 같다.

두 번째 예제는 입력으로 주어진 트리(= 본문에 있는 트리)를 2ドル$번 반사복제한 트리에 관하여 묻고 있다. 이를 그림으로 그리면 다음과 같다.