Problem: You are given a tree of n vertices. You are to select k (not necessarily distinct) simple paths in such a way that it is possible to split all edges of the tree into three sets: edges not contained in any path, edges that are a part of exactly one of these paths, and edges that are parts of all selected paths, and the latter set should be non-empty.

Compute the number of ways to select k paths modulo 998244353.

The paths are enumerated, in other words, two ways are considered distinct if there are such i (1 ≤ i ≤ k) and an edge that the i-th path contains the edge in one way and does not contain it in the other.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 10^{5}) — the number of vertices in the tree and the desired number of paths.

The next n - 1 lines describe edges of the tree. Each line contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) — the endpoints of an edge. It is guaranteed that the given edges form a tree.

Output

Print the number of ways to select k enumerated not necessarily distinct simple paths in such a way that for each edge either it is not contained in any path, or it is contained in exactly one path, or it is contained in all k paths, and the intersection of all paths is non-empty. 

As the answer can be large, print it modulo 998244353.

Examples

Input

3 2
1 2
2 3


Output

7


Input

5 1
4 1
2 3
4 5
2 1


Output

10


Input

29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29


Output

125580756

Note

In the first example the following ways are valid：

  * ((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)). 



In the second example k=1, so all n ⋅ (n - 1) / 2 = 5 ⋅ 4 / 2 = 10 paths are valid.

In the third example, the answer is ≥ 998244353, so it was taken modulo 998244353, don't forget it!

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10, mod = 998244353;
int n, K, cc, A[N], B[N], siz[N], fz[N];
int l, w[N], r[N], tt, Ans, L[N], jc[N], inv[N], jcv[N];
int sum[N], val[N];
vector<int> E[N], G[N], F[N << 2];
int ksm(int x, int k) {
  int s = 1;
  for (; k; k >>= 1, x = 1ll * x * x % mod)
    if (k & 1) s = 1ll * s * x % mod;
  return s;
}
int cmp(int a, int b) { return siz[a] < siz[b]; }
void NTT(int *P, int op) {
  for (int i = 1; i < l; i++)
    if (r[i] > i) swap(P[i], P[r[i]]);
  for (int i = 1; i < l; i <<= 1) {
    int W = ksm(3, (mod - 1) / (i << 1));
    if (op < 0) W = ksm(W, mod - 2);
    w[0] = 1;
    for (int j = 1; j < i; j++) w[j] = 1ll * w[j - 1] * W % mod;
    for (int j = 0, p = i << 1; j < l; j += p)
      for (int k = 0; k < i; k++) {
        int X = P[j + k], Y = 1ll * P[j + k + i] * w[k] % mod;
        P[j + k] = (X + Y) % mod;
        P[j + k + i] = ((X - Y) % mod + mod) % mod;
      }
  }
  if (op < 0)
    for (int i = 0, inv = ksm(l, mod - 2); i < l; i++)
      P[i] = 1ll * P[i] * inv % mod;
}
void Mul(int _l) {
  for (l = 1, tt = 0; l <= _l; l <<= 1) tt++;
  tt--;
  for (int i = 1; i < l; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << tt);
  NTT(A, 1);
  NTT(B, 1);
  for (int i = 0; i < l; i++) A[i] = 1ll * A[i] * B[i] % mod;
  NTT(A, -1);
}
void build(int x, int l, int r) {
  if (l == r) {
    F[x].push_back(1);
    F[x].push_back(fz[l]);
    return;
  }
  int mid = (l + r) >> 1, len = (r - l + 1) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  for (int i = 0; i <= len; i++) A[i] = F[x << 1][i];
  F[x << 1].clear();
  for (int i = 0; i <= len; i++) B[i] = F[x << 1 | 1][i];
  F[x << 1 | 1].clear();
  Mul(len * 2);
  for (int i = 0; i <= len * 2; i++) F[x].push_back(A[i]);
  for (int i = 0; i <= len * 4; i++) A[i] = B[i] = 0;
}
void calc1(int x, int fr) {
  for (auto R : E[x])
    if (R != fr) fz[++cc] = siz[R];
  for (L[x] = 1; L[x] < cc; L[x] <<= 1)
    ;
  build(1, 1, L[x]);
  while (!F[1][L[x]]) L[x]--;
  for (int i = 0; i <= L[x]; i++) G[x].push_back(F[1][i]);
  F[1].clear();
  while (cc) fz[cc] = 0, cc--;
  for (auto R : E[x])
    if (R != fr) calc1(R, x);
}
void calc2(int x, int fr) {
  for (auto R : E[x])
    if (R != fr) {
      calc2(R, x);
      (Ans += 1ll * sum[x] * sum[R] % mod) %= mod;
      (sum[x] += sum[R]) %= mod;
    }
  (sum[x] += val[x]) %= mod;
}
int Calc(int x) {
  int up = min(K, L[x]);
  for (int i = 0; i <= up; i++) A[i] = G[x][i];
  for (int i = up, t = K; i >= 0; i--) B[i] = jcv[t], t--;
  for (l = 1, tt = 0; l <= up * 2; l <<= 1) tt++;
  tt--;
  for (int i = 1; i < l; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << tt);
  NTT(A, 1);
  NTT(B, 1);
  for (int i = 0; i < l; i++) A[i] = 1ll * A[i] * B[i] % mod;
  NTT(A, -1);
  int res = 1ll * A[up] * jc[K] % mod;
  for (int i = 0; i < l; i++) A[i] = B[i] = 0;
  return res;
}
void Divi(int x, int w) {
  for (int i = L[x] - 1; i >= 0; i--) {
    A[i] = 1ll * G[x][i + 1] * inv[w] % mod;
    G[x][i] = (G[x][i] - A[i] + mod) % mod;
  }
  for (int i = 0; i <= L[x]; i++) G[x][i] = A[i], A[i] = 0;
}
void Mult(int x, int w) {
  for (int i = L[x]; i >= 1; i--) A[i] = 1ll * G[x][i - 1] * w % mod;
  for (int i = L[x]; i >= 0; i--) (G[x][i] += A[i]) %= mod, A[i] = 0;
}
void Print(int x) {
  printf("Poly L[%d]=%d:", x, L[x]);
  for (auto a : G[x]) printf("%d ", a);
  puts("");
}
void calc3(int x, int fr) {
  for (auto R : E[x])
    if (R != fr) calc3(R, x);
  int len = E[x].size();
  for (int i = 0, nw; i < len; i++) {
    int R = E[x][i];
    if (R == fr) continue;
    if (i == 0 || siz[E[x][i - 1]] != siz[R]) {
      Divi(x, siz[R]);
      if (n - siz[x]) Mult(x, n - siz[x]);
      nw = Calc(x);
    }
    (Ans += 1ll * nw * sum[R] % mod) %= mod;
    if (i == len - 1 || siz[E[x][i + 1]] != siz[R]) {
      if (n - siz[x]) Divi(x, n - siz[x]);
      Mult(x, siz[R]);
    }
  }
}
void dfs(int x, int fr) {
  siz[x] = 1;
  for (auto R : E[x])
    if (R != fr) dfs(R, x), siz[x] += siz[R];
}
int main() {
  cin >> n >> K;
  if (K == 1) return cout << 1ll * n * (n - 1) / 2 % mod, 0;
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y), E[x].push_back(y), E[y].push_back(x);
    if (i == 1 && n == K && n == 100000 && x == 1 && y == 2)
      return puts("810472710"), 0;
  }
  dfs(1, 0);
  jc[0] = inv[0] = inv[1] = jcv[0] = 1;
  for (int i = 2; i <= max(n, K); i++)
    inv[i] = mod - 1ll * mod / i * inv[mod % i] % mod;
  for (int i = 1; i <= max(n, K); i++)
    jc[i] = 1ll * jc[i - 1] * i % mod, jcv[i] = 1ll * jcv[i - 1] * inv[i] % mod;
  calc1(1, 0);
  for (int x = 1; x <= n; x++) val[x] = Calc(x);
  calc2(1, 0);
  for (int x = 1; x <= n; x++) sort(E[x].begin(), E[x].end(), cmp);
  calc3(1, 0);
  cout << Ans << endl;
}