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>
namespace in {
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int getc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
template <typename T>
inline void read(T &t) {
  t = 0;
  int f = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    t = t * 10 + ch - 48;
    ch = getc();
  }
  if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
}  // namespace in
namespace out {
char buffer[1 << 21];
int p1 = -1;
const int p2 = (1 << 21) - 1;
inline void flush() { fwrite(buffer, 1, p1 + 1, stdout), p1 = -1; }
inline void putc(const char &x) {
  if (p1 == p2) flush();
  buffer[++p1] = x;
}
template <typename T>
void write(T x) {
  static char buf[15];
  static int len = -1;
  if (x >= 0) {
    do {
      buf[++len] = x % 10 + 48, x /= 10;
    } while (x);
  } else {
    putc('-');
    do {
      buf[++len] = -(x % 10) + 48, x /= 10;
    } while (x);
  }
  while (len >= 0) putc(buf[len]), --len;
}
}  // namespace out
using namespace std;
template <const int mod>
struct modint {
  int x;
  modint<mod>(int o = 0) { x = o; }
  modint<mod> &operator=(int o) { return x = o, *this; }
  modint<mod> &operator+=(modint<mod> o) {
    return x = x + o.x >= mod ? x + o.x - mod : x + o.x, *this;
  }
  modint<mod> &operator-=(modint<mod> o) {
    return x = x - o.x < 0 ? x - o.x + mod : x - o.x, *this;
  }
  modint<mod> &operator*=(modint<mod> o) {
    return x = 1ll * x * o.x % mod, *this;
  }
  modint<mod> &operator^=(int b) {
    modint<mod> a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint<mod> &operator/=(modint<mod> o) { return *this *= o ^= mod - 2; }
  modint<mod> &operator+=(int o) {
    return x = x + o >= mod ? x + o - mod : x + o, *this;
  }
  modint<mod> &operator-=(int o) {
    return x = x - o < 0 ? x - o + mod : x - o, *this;
  }
  modint<mod> &operator*=(int o) { return x = 1ll * x * o % mod, *this; }
  modint<mod> &operator/=(int o) {
    return *this *= ((modint<mod>(o)) ^= mod - 2);
  }
  template <class I>
  friend modint<mod> operator+(modint<mod> a, I b) {
    return a += b;
  }
  template <class I>
  friend modint<mod> operator-(modint<mod> a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint<mod> operator*(modint<mod> a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint<mod> operator/(modint<mod> a, I b) {
    return a /= b;
  }
  friend modint<mod> operator^(modint<mod> a, int b) { return a ^= b; }
  friend bool operator==(modint<mod> a, int b) { return a.x == b; }
  friend bool operator!=(modint<mod> a, int b) { return a.x != b; }
  bool operator!() { return !x; }
  modint<mod> operator-() { return x ? mod - x : 0; }
  modint<mod> &operator++(int) { return *this += 1; }
};
const int N = 2e5 + 5;
const int mod = 998244353;
const modint<mod> GG = 3, Ginv = modint<mod>(1) / 3, I = 86583718;
struct poly {
  vector<modint<mod>> a;
  modint<mod> &operator[](int i) { return a[i]; }
  int size() { return a.size(); }
  void resize(int n) { a.resize(n); }
  void reverse() { std::reverse(a.begin(), a.end()); }
};
int rev[N];
inline poly one() {
  poly a;
  a.a.push_back(1);
  return a;
}
inline int ext(int n) {
  int k = 0;
  while ((1 << k) < n) k++;
  return k;
}
inline void init(int k) {
  int n = 1 << k;
  for (int i = 0; i < n; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
inline void ntt(poly &a, int k, int typ) {
  int n = 1 << k;
  for (int i = 0; i < n; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int mid = 1; mid < n; mid <<= 1) {
    modint<mod> wn = (typ > 0 ? GG : Ginv) ^ ((mod - 1) / (mid << 1));
    for (int r = mid << 1, j = 0; j < n; j += r) {
      modint<mod> w = 1;
      for (int k = 0; k < mid; k++, w = w * wn) {
        modint<mod> x = a[j + k], y = w * a[j + k + mid];
        a[j + k] = x + y, a[j + k + mid] = x - y;
      }
    }
  }
  if (typ < 0) {
    modint<mod> inv = modint<mod>(1) / n;
    for (int i = 0; i < n; i++) a[i] *= inv;
  }
}
poly operator+(poly a, poly b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] += b[i];
  return a;
}
poly operator-(poly a, poly b) {
  int n = max(a.size(), b.size());
  a.resize(n), b.resize(n);
  for (int i = 0; i < n; i++) a[i] -= b[i];
  return a;
}
inline poly operator*(poly a, poly b) {
  int n = a.size() + b.size() - 1, k = ext(n);
  a.resize(1 << k), b.resize(1 << k), init(k);
  ntt(a, k, 1);
  ntt(b, k, 1);
  for (int i = 0; i < (1 << k); i++) a[i] *= b[i];
  ntt(a, k, -1), a.resize(n);
  return a;
}
inline poly operator*(poly a, modint<mod> b) {
  for (int i = 0; i < a.size(); i++) a[i] *= b;
  return a;
}
inline poly operator/(poly a, modint<mod> b) {
  for (int i = 0; i < a.size(); i++) a[i] /= b;
  return a;
}
inline poly operator-(poly a) {
  for (int i = 0; i < a.size(); i++) a[i] = -a[i];
  return a;
}
int n, k;
vector<int> e[N];
modint<mod> fac[N], ifac[N], s[N], sum[N], dsum[N];
int fa[N], sz[N];
poly work1(int l, int r, vector<int> &a) {
  if (l == r) {
    poly f;
    f.resize(2);
    f[0] = 1;
    f[1] = a[l];
    return f;
  }
  return work1(l, (l + r >> 1), a) * work1((l + r >> 1) + 1, r, a);
}
pair<poly, poly> work2(int l, int r, vector<pair<int, modint<mod>>> &a) {
  if (l == r) {
    poly F, G;
    F.resize(2);
    G.resize(1);
    F[0] = 1;
    F[1] = a[l].first;
    G[0] = a[l].second;
    return {F, G};
  }
  auto L = work2(l, (l + r >> 1), a), R = work2((l + r >> 1) + 1, r, a);
  return {L.first * R.first, L.first * R.second + L.second * R.first};
}
void dfs1(int u) {
  vector<int> tmp;
  sz[u] = 1;
  for (auto v : e[u])
    if (v != fa[u]) fa[v] = u, dfs1(v), sz[u] += sz[v], tmp.push_back(sz[v]);
  poly f;
  if (sz[u] == 1)
    f.resize(1), f[0] = 1;
  else
    f = work1(0, tmp.size() - 1, tmp);
  for (int i = 0; i <= k && i < f.size(); i++)
    s[u] += fac[k] * ifac[k - i] * f[i];
  for (auto v : e[u])
    if (v != fa[u]) sum[u] += sum[v];
  sum[u] += s[u];
}
void dfs2(int u) {
  dsum[u] = s[u] + dsum[fa[u]];
  for (auto v : e[u])
    if (v != fa[u]) dfs2(v);
}
signed main() {
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i;
  ifac[N - 1] = 1 / fac[N - 1];
  for (int i = N - 1; i; i--) ifac[i - 1] = ifac[i] * i;
  in::read(n, k);
  if (k == 1) {
    out::write((modint<mod>(n) * (n - 1) / 2).x);
    out::flush();
    return 0;
  }
  for (int i = 1, u, v; i < n; i++)
    in::read(u, v), e[u].push_back(v), e[v].push_back(u);
  dfs1(1);
  dfs2(1);
  modint<mod> ans = 0;
  for (int i = 1; i <= n; i++) ans += s[i] * (sum[1] - sum[i] + s[i] - dsum[i]);
  ans /= 2;
  for (int u = 1; u <= n; u++) {
    if (sz[u] == 1) continue;
    poly F;
    F.resize(2);
    F[0] = 1;
    F[1] = n - sz[u];
    vector<pair<int, modint<mod>>> tmp;
    for (auto v : e[u])
      if (v != fa[u]) tmp.push_back({sz[v], sum[v]});
    F = F * work2(0, tmp.size() - 1, tmp).second;
    for (int i = 0; i <= k && i < F.size(); i++)
      ans += fac[k] * ifac[k - i] * F[i];
  }
  out::write(ans.x);
  out::flush();
  return 0;
}