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;
template <typename T>
void pfill(T* pst, const T* ped, T val) {
  for (; pst != ped; *(pst++) = val)
    ;
}
template <typename T>
void pcopy(T* pst, const T* ped, T* pval) {
  for (; pst != ped; *(pst++) = *(pval++))
    ;
}
const int N = 262144;
const int Mod = 998244353;
const int bzmax = 19;
const int g = 3;
void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
int inv(int a) {
  int x, y;
  exgcd(a, Mod, x, y);
  return (x < 0) ? (x + Mod) : (x);
}
template <const int Mod = ::Mod>
class Z {
 public:
  int v;
  Z() : v(0) {}
  Z(int v) : v(v) {}
  Z(long long x) : v(x % Mod) {}
  Z operator+(Z b) {
    int x = v + b.v;
    return Z((x >= Mod) ? (x - Mod) : (x));
  }
  Z operator-(Z b) {
    int x = v - b.v;
    return Z((x < 0) ? (x + Mod) : (x));
  }
  Z operator*(Z b) { return Z(1ll * v * b.v); }
  Z operator~() { return inv(v); }
  Z operator-() { return Z(0) - *this; }
  Z& operator+=(Z b) { return *this = *this + b; }
  Z& operator-=(Z b) { return *this = *this - b; }
  Z& operator*=(Z b) { return *this = *this * b; }
};
Z<> qpow(Z<> a, int p) {
  if (p < Mod - 1) p += Mod - 1;
  Z<> rt = 1, pa = a;
  for (; p; p >>= 1, pa = pa * pa) {
    if (p & 1) {
      rt = rt * pa;
    }
  }
  return rt;
}
class NTT {
 private:
  Z<> gn[bzmax + 4], _gn[bzmax + 4];

 public:
  NTT() {
    for (int i = 0; i <= bzmax; i++) {
      gn[i] = qpow(Z<>(g), (Mod - 1) >> i);
      _gn[i] = qpow(Z<>(g), -((Mod - 1) >> i));
    }
  }
  void operator()(Z<>* f, int len, int sgn) {
    for (int i = 1, j = len >> 1, k; i < len - 1; i++, j += k) {
      if (i < j) swap(f[i], f[j]);
      for (k = len >> 1; k <= j; j -= k, k >>= 1)
        ;
    }
    Z<>*wn = (sgn > 0) ? (gn + 1) : (_gn + 1), w, a, b;
    for (int l = 2, hl; l <= len; l <<= 1, wn++) {
      hl = l >> 1, w = 1;
      for (int i = 0; i < len; i += l, w = 1) {
        for (int j = 0; j < hl; j++, w *= *wn) {
          a = f[i + j], b = f[i + j + hl] * w;
          f[i + j] = a + b;
          f[i + j + hl] = a - b;
        }
      }
    }
    if (sgn < 0) {
      Z<> invlen = ~Z<>(len);
      for (int i = 0; i < len; i++) {
        f[i] *= invlen;
      }
    }
  }
  int correct_len(int len) {
    int m = 1;
    for (; m <= len; m <<= 1)
      ;
    return m;
  }
} NTT;
void pol_inverse(Z<>* f, Z<>* g, int n) {
  static Z<> A[N];
  if (n == 1) {
    g[0] = ~f[0];
  } else {
    int hn = (n + 1) >> 1, t = NTT.correct_len(n << 1 | 1);
    pol_inverse(f, g, hn);
    pcopy(A, A + n, f);
    pfill(A + n, A + t, Z<>(0));
    pfill(g + hn, g + t, Z<>(0));
    NTT(A, t, 1);
    NTT(g, t, 1);
    for (int i = 0; i < t; i++) {
      g[i] = g[i] * (Z<>(2) - g[i] * A[i]);
    }
    NTT(g, t, -1);
    pfill(g + n, g + t, Z<>(0));
  }
}
vector<Z<> > operator+(vector<Z<> > A, vector<Z<> > B) {
  int n = A.size(), m = B.size();
  int t = max(n, m);
  A.resize(t), B.resize(t);
  for (int i = 0; i < t; i++) {
    A[i] += B[i];
  }
  return A;
}
vector<Z<> > operator-(vector<Z<> > A, vector<Z<> > B) {
  int n = A.size(), m = B.size();
  int t = max(n, m);
  A.resize(t), B.resize(t);
  for (int i = 0; i < t; i++) {
    A[i] -= B[i];
  }
  return A;
}
vector<Z<> > operator*(vector<Z<> > A, vector<Z<> > B) {
  int n = A.size(), m = B.size();
  int k = NTT.correct_len(n + m - 1);
  if (n < 20 || m < 20) {
    vector<Z<> > rt(n + m - 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        rt[i + j] += A[i] * B[j];
      }
    }
    return rt;
  }
  A.resize(k), B.resize(k);
  NTT(A.data(), k, 1);
  NTT(B.data(), k, 1);
  for (int i = 0; i < k; i++) {
    A[i] *= B[i];
  }
  NTT(A.data(), k, -1);
  A.resize(n + m - 1);
  return A;
}
vector<Z<> > operator~(vector<Z<> > f) {
  int n = f.size(), t = NTT.correct_len((n << 1) | 1);
  vector<Z<> > rt(t);
  f.resize(t);
  pol_inverse(f.data(), rt.data(), n);
  rt.resize(n);
  return rt;
}
vector<Z<> > operator/(vector<Z<> > A, vector<Z<> > B) {
  int n = A.size(), m = B.size();
  if (n < m) {
    return vector<Z<> >{0};
  }
  int r = n - m + 1;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  A.resize(r), B.resize(r);
  A = A * ~B;
  A.resize(r);
  reverse(A.begin(), A.end());
  return A;
}
vector<Z<> > operator%(vector<Z<> > A, vector<Z<> > B) {
  int n = A.size(), m = B.size();
  if (n < m) {
    return A;
  }
  if (m == 1) {
    return vector<Z<> >{0};
  }
  A = A - A / B * B;
  A.resize(m - 1);
  return A;
}
Z<> Inv[N];
void init_inv(int n) {
  Inv[0] = 0, Inv[1] = 1;
  for (int i = 2; i <= n; i++) {
    Inv[i] = Inv[Mod % i] * Z<>((Mod - (Mod / i)));
  }
}
Z<> fac[N], _fac[N];
Z<> comb(int n, int m) {
  return (n < m) ? (0) : (fac[n] * _fac[m] * _fac[n - m]);
}
void init_fac(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i;
  }
  _fac[n] = ~fac[n];
  for (int i = n; i; i--) {
    _fac[i - 1] = _fac[i] * i;
  }
}
int n, K;
int sz[N];
vector<int> G[N];
void dfs1(int p, int fa) {
  sz[p] = 1;
  for (auto& e : G[p]) {
    if (e ^ fa) {
      dfs1(e, p);
      sz[p] += sz[e];
    }
  }
}
vector<Z<> > dividing(int n, Z<>* a) {
  if (n == 1) {
    return vector<Z<> >{1, *a};
  }
  int hn = n >> 1;
  return dividing(hn, a) * dividing(n - hn, a + hn);
}
vector<Z<> > divide2(vector<Z<> > F, int a1, int a0) {
  Z<> b = 0, _a1 = Inv[a1];
  for (int i = (signed)F.size() - 1; i; i--) {
    b = F[i] * _a1;
    F[i] = b, F[i - 1] -= b * a0;
  }
  assert(!F[0].v);
  for (int i = 0; i < (signed)F.size() - 1; i++) {
    F[i] = F[i + 1];
  }
  F.pop_back();
  return F;
}
Z<> ans = 0;
Z<> dfs2(int p, int fa) {
  vector<Z<> > Sz;
  if (fa) {
    Sz.push_back(n - sz[p]);
  }
  for (auto& e : G[p]) {
    if (e ^ fa) {
      Sz.push_back(sz[e]);
    }
  }
  vector<Z<> > H = dividing(Sz.size(), Sz.data());
  sort(G[p].begin(), G[p].end(),
       [&](const int& a, const int& b) { return sz[a] < sz[b]; });
  int lst = -1;
  vector<Z<> > f;
  Z<> rt = 0, tmp, cur;
  for (auto& e : G[p]) {
    if (e == fa) {
      continue;
    }
    if (sz[e] != lst) {
      f = divide2(H, sz[e], 1);
      if ((signed)f.size() > K + 1) {
        f.resize(K + 1);
      }
      cur = 0;
      for (int i = 0; i < (signed)f.size(); i++) {
        cur += f[i] * comb(K, i) * fac[i];
      }
    }
    tmp = dfs2(e, p);
    lst = sz[e];
    ans += tmp * (rt + cur);
    rt += tmp;
  }
  if (fa) {
    int x = n - sz[p];
    f = divide2(H, x, 1);
    if ((signed)f.size() > K + 1) {
      f.resize(K + 1);
    }
    tmp = 0;
    for (int i = 0; i < (signed)f.size(); i++) {
      tmp += f[i] * comb(K, i) * fac[i];
    }
    rt += tmp;
  }
  return rt;
}
int main() {
  scanf("%d%d", &n, &K);
  if (K == 1 || n == 1) {
    printf("%d\n", ((n * 1ll * (n - 1)) >> 1) % Mod);
    return 0;
  }
  init_inv(n);
  init_fac(K);
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(1, 0);
  printf("%d\n", ans.v);
  return 0;
}