하나의 목표

공화국 Never에는 $n$개의 도시와 $n - 1$개의 도로가 있다. 도시에는 1번부터 $n$번까지 번호가 붙어 있다. 각 도로는 두 도시를 잇고 양방향으로 통행할 수 있다. 임의의 두 도시는 도로를 따라 서로 오갈 수 있다. 거리 $d(u, v)$는 도시 $u$에서 도시 $v$까지 이동하는 데 필요한 도로 수의 최솟값이다.

$k$명의 친구가 만나려고 한다. $i$번째 친구는 도시 $a_i$에 산다. 친구들은 $\sum_{i=1}^{k}{d(v, a_i)}$가 최소가 되는 도시 $v$를 고른다. 그런 도시가 여러 개면 번호가 가장 작은 도시를 고른다.

친구들이 어디에 사는지는 알 수 없다. 각 친구는 $n$개의 도시 중 어디에든 살 수 있으므로 경우의 수는 모두 $n^k$가지이다. 이 $n^k$가지 경우에서 친구들이 고른 도시 번호를 모두 더한 값을 구하라. 답은 998244353으로 나눈 나머지로 출력한다.

첫 줄에 두 정수 $n$과 $k$가 주어진다($2 \le n, k \le 30000$). 이어지는 $n - 1$개의 줄에는 각각 두 정수 $u_i$와 $v_i$가 주어지며, 이는 $i$번째 도로가 잇는 두 도시의 번호이다($1 \le u_i, v_i \le n$, $u_i \ne v_i$). 임의의 두 도시는 도로를 따라 서로 오갈 수 있다고 보장된다.

$n^k$가지 경우 모두에서 고른 도시 번호의 합을 998244353으로 나눈 나머지를 출력한다.

첫 번째 예에서 도시는 3개, 친구는 2명이므로 경우의 수는 $3^2 = 9$가지이다. 이 중 3가지는 두 친구가 같은 도시에 살고, 그 도시를 고른다. 나머지 6가지는 두 친구가 서로 다른 도시에 살고, 도시 1을 고른다. 합은 $(1 + 2 + 3) + 6 \cdot 1 = 12$이다.