K Paths

n개의 정점으로 이루어진 트리가 주어진다. 트리의 모든 간선을 어떤 경로에도 포함되지 않는 간선, 이 경로들 중 정확히 하나에 포함되는 간선, 선택한 모든 경로에 포함되는 간선이라는 세 집합으로 나눌 수 있고, 마지막 집합이 비어 있지 않도록 k개의 단순 경로를 선택해야 한다. 경로들은 서로 달라도 되고 같아도 된다.

k개의 경로를 선택하는 방법의 수를 998244353으로 나눈 나머지를 계산한다.

경로에는 순서가 있다. 다시 말해, 어떤 i (1 ≤ i ≤ k)와 어떤 간선이 존재하여 한 방법에서는 i-th번째 경로가 그 간선을 포함하고 다른 방법에서는 포함하지 않는다면, 두 방법은 서로 다른 것으로 간주한다.

첫 번째 줄에 트리의 정점 수와 원하는 경로 수를 나타내는 두 정수 n와 k (1 ≤ n, k ≤ $10^{5}$)가 주어진다.

다음 n - 1개의 줄에는 트리의 간선이 주어진다. 각 줄에는 간선의 양 끝점을 나타내는 두 정수 a와 b (1 ≤ a, b ≤ n, a ≠ b)가 주어진다. 주어진 간선들이 트리를 이룬다는 것이 보장된다.

각 간선이 어떤 경로에도 포함되지 않거나, 정확히 하나의 경로에 포함되거나, k개의 모든 경로에 포함되고, 모든 경로의 교집합이 비어 있지 않도록 순서가 있으며 서로 달라도 되고 같아도 되는 k개의 단순 경로를 선택하는 방법의 수를 출력한다.

답이 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

첫 번째 예제에서는 다음 방법들이 유효하다：

• ((1,2), (1,2)),
• ((1,2), (1,3)),
• ((1,3), (1,2)),
• ((1,3), (1,3)),
• ((1,3), (2,3)),
• ((2,3), (1,3)),
• ((2,3), (2,3)).

두 번째 예제에서는 k=1이므로, n ⋅ (n - 1) / 2 = 5 ⋅ 4 / 2 = 10개의 모든 경로가 유효하다.

세 번째 예제에서는 답이 ≥ 998244353이므로 998244353으로 나눈 나머지를 취했다. 이를 잊지 말아야 한다!