반사복제된 트리

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

• $T$의 각 리프 노드 $L$에 대하여, 트리 $T$를 통째로 복제한 뒤 복제본에서 $L$에 해당하는 노드를 원래 트리의 $L$과 겹친다. 복제본은 원래 트리와 같은 위상을 가진다.

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

$N$개의 노드를 가진 트리가 주어진다. 이 트리를 $K$번 반사복제했을 때, 모든 노드 쌍 사이의 거리를 $10^{9} + 7$로 나눈 나머지를 구하시오. $dist(v_1, v_2)$는 두 노드 $v_1$, $v_2$를 잇는 경로 위의 간선 개수이고, $V$는 전체 노드의 집합이다. 구할 값은 다음과 같다.

$\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번 반사복제한 트리는 다음 그림과 같다.