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 = 262333, mod = 998244353, G = 3, inv2 = (mod + 1) >> 1;
int read() {
  int ret = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) ret = ret * 10 + (c ^ 48), c = getchar();
  return ret;
}
namespace Math {
int fac[N], ifac[N], inv[N];
int add(int x) { return x >= mod ? x - mod : x; }
int sub(int x) { return x < 0 ? x + mod : x; }
void Add(int &x, int y) { x = add(x + y); }
void Sub(int &x, int y) { x = sub(x - y); }
int mul(int x, int y) { return 1ll * x * y % mod; }
int qpow(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = mul(x, x))
    if (y & 1) res = mul(res, x);
  return res;
}
int getinv(int x) { return qpow(x, mod - 2); }
void initmath() {
  fac[0] = 1;
  for (int i = 1; i < N; ++i) fac[i] = mul(fac[i - 1], i);
  ifac[N - 1] = getinv(fac[N - 1]);
  for (int i = N - 2; ~i; --i) ifac[i] = mul(ifac[i + 1], i + 1);
  inv[0] = inv[1] = 1;
  for (int i = 2; i < N; ++i) inv[i] = mul(mod - mod / i, inv[mod % i]);
}
int P(int x, int y) { return 1ll * fac[x] * ifac[x - y] % mod; }
}  // namespace Math
using namespace Math;
namespace Poly {
int m, L, rev[N];
void ntt(int *a, int n, int op) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1) {
    int wn = qpow(G, (mod - 1) / (i << 1));
    if (!~op) wn = getinv(wn);
    for (int j = 0; j < n; j += i << 1) {
      int w = 1;
      for (int k = 0; k < i; ++k, w = mul(w, wn)) {
        int x = a[j + k], y = mul(w, a[i + j + k]);
        a[j + k] = add(x + y);
        a[i + j + k] = sub(x - y);
      }
    }
  }
  if (!~op)
    for (int i = 0, iv = getinv(n); i < n; ++i) a[i] = mul(iv, a[i]);
}
void reget(int n) {
  for (m = 1, L = 0; m < n; m <<= 1, ++L)
    ;
  for (int i = 0; i < m; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
void polymul(int *a, int *b, int *c) {
  ntt(a, m, 1);
  ntt(b, m, 1);
  for (int i = 0; i < m; ++i) c[i] = mul(a[i], b[i]);
  ntt(c, m, -1);
}
void polymult(int *a, int *b, int *c, int dega, int degb) {
  static int A[N], B[N];
  reget(dega + degb - 1);
  copy(a, a + dega, A);
  copy(b, b + degb, B);
  polymul(A, B, c);
  fill(c + dega + degb - 1, c + m, 0);
  fill(A, A + m, 0);
  fill(B, B + m, 0);
}
void polydec(int *a, int deg, int v) {
  static int A[N];
  int coe = getinv(v), iv;
  for (int i = 0; i < deg; ++i) A[i] = a[i], a[i] = 0;
  for (int i = deg - 1; i; --i) {
    if (A[i]) {
      a[i - 1] = iv = mul(A[i], coe);
      Sub(A[i], mul(iv, coe));
      Sub(A[i - 1], iv);
    }
  }
  fill(A, A + deg, 0);
}
void polyadd(int *a, int deg, int v) {
  for (int i = deg; i; --i) Add(a[i], mul(a[i - 1], v));
}
}  // namespace Poly
using namespace Poly;
namespace DreamLolita {
int n, K, tot, ans;
int head[N], siz[N], now[N], val[N], tmp[N];
int f[N], g[N], h[N], F[20][N];
struct Tway {
  int v, nex;
} e[N];
void add(int u, int v) {
  e[++tot] = (Tway){v, head[u]};
  head[u] = tot;
  e[++tot] = (Tway){u, head[v]};
  head[v] = tot;
}
void solve(int l, int r, int d) {
  if (l == r) {
    F[d][1] = val[l];
    F[d][0] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  solve(l, mid, d);
  solve(mid + 1, r, d + 1);
  polymult(F[d], F[d + 1], F[d], mid - l + 2, r - mid + 1);
  fill(F[d + 1], F[d + 1] + Poly::m, 0);
}
int calc(int *a, int len) {
  int res = 0, lim = min(len, K);
  for (int i = 0; i <= lim; ++i) Add(res, mul(a[i], P(K, i)));
  return res;
}
bool cmp(int x, int y) { return siz[x] < siz[y]; }
void dfs1(int x, int fa) {
  siz[x] = 1;
  int son = 0;
  for (int i = head[x]; i; i = e[i].nex) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs1(v, x);
    Add(g[x], g[v]);
    siz[x] += siz[v];
  }
  for (int i = head[x]; i; i = e[i].nex)
    if (e[i].v != fa) val[++son] = siz[e[i].v];
  ;
  if (!son) {
    f[x] = g[x] = 1;
    return;
  }
  solve(1, son, 0);
  f[x] = calc(F[0], son);
  Add(g[x], f[x]);
  son = 0;
  for (int i = head[x]; i; i = e[i].nex)
    if (e[i].v != fa) val[++son] = e[i].v;
  sort(val + 1, val + son + 1, cmp);
  for (int i = 0; i <= son; ++i) tmp[i] = F[0][i];
  for (int i = 1; i <= son; ++i) {
    if (siz[val[i]] == siz[val[i - 1]])
      h[val[i]] = h[val[i - 1]];
    else {
      for (int j = 0; j <= son; ++j) now[j] = tmp[j];
      polydec(now, son + 1, siz[val[i]]);
      polyadd(now, son, n - siz[x]);
      h[val[i]] = calc(now, son);
    }
  }
  fill(F[0], F[0] + Poly::m, 0);
  for (int i = 0; i <= son; ++i) now[i] = tmp[i] = 0;
}
void dfs2(int x, int fa) {
  for (int i = head[x]; i; i = e[i].nex) {
    int v = e[i].v;
    if (v == fa) continue;
    Add(ans, mul(sub(h[v] - f[x]), g[v]));
    dfs2(v, x);
  }
}
void solution() {
  initmath();
  n = read();
  K = read();
  if (K == 1) {
    printf("%lld\n", 1ll * n * (n - 1) / 2 % mod);
    return;
  }
  for (int i = 1; i < n; ++i) add(read(), read());
  dfs1(1, 0);
  dfs2(1, 0);
  int sum = 0;
  for (int i = 1; i <= n; ++i) Add(sum, f[i]);
  sum = mul(sum, sum);
  for (int i = 1; i <= n; ++i) Sub(sum, mul(f[i], f[i]));
  sum = mul(sum, inv2);
  Add(ans, sum);
  printf("%d\n", ans);
}
}  // namespace DreamLolita
int main() {
  DreamLolita::solution();
  return 0;
}