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

문제

There are n cities and n − 1 roads in the Republic of Never. The cities are conveniently numbered from 1 to n. Every road connects two cities and can be traversed in both directions. It is possible to move between any two cities using the roads. The distance d(u, v) is defined as the smallest number of roads one needs to use to move from city u to city v.

There are k friends who are looking to meet. The i-th friend lives in city ai. For the meeting, the friends will choose city v such that \(\sum_{i=1}^{k}{d(v, a_i)}\)  is minimum. If there are several such cities, they will choose the one with the smallest number among them.

Unfortunately, you know just the number of friends but nothing about the cities where they live. Every friend might live in any of the n cities; hence, there are nk options overall. You would like to find the sum of the numbers of cities the friends will choose in all the nk options. Output this sum modulo 998 244 353.

입력

The first line of the input contains two integers n and k (2 ≤ n, k ≤ 30 000), denoting the number of cities and the number of friends.

Each of the following n − 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n; ui ≠ vi), denoting the numbers of the cities connected by the i-th road.

It is guaranteed that it is possible to move between any two cities using the roads.

출력

Display the sum of the numbers of cities the friends will choose in all the nk options, modulo 998 244 353.

예제 입력 1

3 2
1 2
1 3

예제 출력 1

12

예제 입력 2

5 3
2 4
5 3
1 3
3 2

예제 출력 2

357

힌트

In the first example, with three cities and two friends, there are 32 = 9 options to consider. In three of these options, the friends are in the same city and they will clearly choose this city for the meeting. In the other six options, the friends are in different cities and they will choose city 1. The total is (1 + 2 + 3) + 6 · 1 = 12.