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>
template <typename _Tp>
void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
template <typename _Tp>
inline void chmax(_Tp &a, const _Tp &b) {
  a = a < b ? b : a;
}
const int max_len = 1 << 18, N = max_len + 5, mod = 998244353, inf = 0x3f3f3f3f;
template <typename _Tp1, typename _Tp2>
inline void add(_Tp1 &a, _Tp2 b) {
  (a += b) >= mod && (a -= mod);
}
template <typename _Tp1, typename _Tp2>
inline void sub(_Tp1 &a, _Tp2 b) {
  (a -= b) < 0 && (a += mod);
}
template <typename _Tp>
inline _Tp _sub(_Tp a, const _Tp &b) {
  (a += mod - b) >= mod && (a -= mod);
  return a;
}
long long ksm(long long a, long long b = mod - 2) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return res;
}
void print(const std::vector<int> &a) {
  for (auto it : a) printf("%d ", it);
  printf("\n");
}
inline std::vector<int> operator<<(std::vector<int> a, unsigned int b) {
  return a.insert(a.begin(), b, 0), a;
}
inline std::vector<int> operator<<=(std::vector<int> &a, unsigned int b) {
  return a.insert(a.begin(), b, 0), a;
}
inline std::vector<int> operator>>(const std::vector<int> &a, unsigned int b) {
  return b >= a.size() ? std::vector<int>()
                       : std::vector<int>{a.begin() + b, a.end()};
}
inline std::vector<int> operator>>=(std::vector<int> &a, unsigned int b) {
  return a = b >= a.size() ? std::vector<int>()
                           : std::vector<int>{a.begin() + b, a.end()};
}
std::vector<int> operator+=(std::vector<int> &a, const std::vector<int> &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (unsigned int i = 0; i < b.size(); ++i) add(a[i], b[i]);
  return a;
}
inline std::vector<int> operator+(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp += b;
  return tmp;
}
std::vector<int> operator-=(std::vector<int> &a, const std::vector<int> &b) {
  if (b.size() > a.size()) a.resize(b.size());
  for (unsigned int i = 0; i < b.size(); ++i) sub(a[i], b[i]);
  return a;
}
inline std::vector<int> operator-(const std::vector<int> &a,
                                  const std::vector<int> &b) {
  std::vector<int> tmp(a);
  tmp -= b;
  return tmp;
}
const unsigned long long Omg = ksm(3, (mod - 1) / max_len);
unsigned long long Omgs[N];
void setup() {
  Omgs[max_len / 2] = 1;
  for (int i = max_len / 2 + 1; i < max_len; ++i)
    Omgs[i] = Omgs[i - 1] * Omg % mod;
  for (int i = max_len / 2 - 1; i > 0; --i) Omgs[i] = Omgs[i << 1];
}
unsigned int rev[N];
unsigned int getlen(unsigned int len) {
  unsigned int limit = 1;
  while (limit < len) limit <<= 1;
  for (unsigned int i = 0; i < limit; ++i)
    rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? limit >> 1 : 0);
  return limit;
}
void dft(unsigned long long *A, unsigned int limit) {
  for (unsigned int i = 0; i < limit; ++i)
    if (i < rev[i]) std::swap(A[i], A[rev[i]]);
  for (unsigned int len = 1; len < limit; len <<= 1) {
    if (len == 262144u)
      for (unsigned int i = 0; i < limit; ++i) A[i] %= mod;
    for (unsigned int i = 0; i < limit; i += len << 1) {
      unsigned long long *p = A + i, *q = A + i + len, *w = Omgs + len;
      for (unsigned int j = 0; j < len; ++j, ++p, ++q, ++w) {
        const unsigned long long tp = *q * *w % mod;
        *q = *p + mod - tp, *p += tp;
      }
    }
  }
  for (unsigned int i = 0; i < limit; ++i) A[i] %= mod;
}
void idft(unsigned long long *A, unsigned int limit) {
  std::reverse(A + 1, A + limit), dft(A, limit);
  unsigned long long inv = mod - (mod - 1) / limit;
  for (unsigned int i = 0; i < limit; ++i) A[i] = A[i] * inv % mod;
}
unsigned long long _f[N], _g[N], _tp[129];
std::vector<int> operator*(const std::vector<int> &a,
                           const std::vector<int> &b) {
  unsigned int len = a.size() + b.size() - 1;
  if (a.size() <= 64u || b.size() <= 64u) {
    memset(_tp, 0, len << 3);
    unsigned int r = 0;
    for (unsigned int i = 0; i < a.size(); ++i) {
      for (unsigned int j = 0; j < b.size(); ++j)
        _tp[i + j] += 1ULL * a[i] * b[j];
      if (++r == 18) {
        r = 0;
        for (unsigned int j = i - 17; j < i + b.size(); ++j) _tp[j] %= mod;
      }
    }
    if (r)
      for (unsigned int j = 0; j < len; ++j) _tp[j] %= mod;
    std::vector<int> c(len);
    for (unsigned int i = 0; i < len; ++i) c[i] = _tp[i];
    return c;
  }
  unsigned int limit = getlen(len);
  memset(_f + a.size(), 0, (limit - a.size()) << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  memset(_g + b.size(), 0, (limit - b.size()) << 3);
  for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
  dft(_f, limit), dft(_g, limit);
  for (unsigned int i = 0; i < limit; ++i) _f[i] = _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
std::vector<int> mul(const std::vector<int> &a, const std::vector<int> &b,
                     unsigned int len, bool need = true) {
  if (a.size() <= 64u || b.size() <= 64u) {
    memset(_tp, 0, len << 3);
    unsigned int r = 0;
    for (unsigned int i = 0; i < a.size(); ++i) {
      for (unsigned int j = 0; j < b.size() && i + j < len; ++j)
        _tp[i + j] += 1ULL * a[i] * b[j];
      if (++r == 18) {
        r = 0;
        for (unsigned int j = i - 17; j < len && j < i + b.size(); ++j)
          _tp[j] %= mod;
      }
    }
    if (r)
      for (unsigned int j = 0; j < len; ++j) _tp[j] %= mod;
    std::vector<int> c(len);
    for (unsigned int i = 0; i < len; ++i) c[i] = _tp[i];
    return c;
  }
  int limit = getlen(len);
  memset(_f + a.size(), 0, (limit - a.size()) << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  dft(_f, limit);
  if (need) {
    memset(_g + b.size(), 0, (limit - b.size()) << 3);
    for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
    dft(_g, limit);
  }
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(len);
  for (unsigned int i = 0; i < len; ++i) ans[i] = _f[i];
  return ans;
}
std::vector<int> mulT(const std::vector<int> &a, const std::vector<int> &b) {
  if (a.size() <= 64u || b.size() <= 64u) {
    std::vector<int> c(a.size() - b.size() + 1);
    for (unsigned int i = 0; i < c.size(); ++i)
      for (unsigned int j = 0; j < b.size(); ++j)
        c[i] = (c[i] + 1ULL * a[i + j] * b[j]) % mod;
    return c;
  }
  int limit = getlen(a.size());
  memset(_f, 0, limit << 3);
  for (unsigned int i = 0; i < a.size(); ++i) _f[i] = a[i];
  memset(_g, 0, limit << 3);
  for (unsigned int i = 0; i < b.size(); ++i) _g[i] = b[i];
  std::reverse(_g, _g + b.size()), dft(_f, limit), dft(_g, limit);
  for (int i = 0; i < limit; ++i) _f[i] = 1ULL * _f[i] * _g[i] % mod;
  idft(_f, limit);
  std::vector<int> ans(a.size() - b.size() + 1);
  for (unsigned int i = b.size() - 1; i < a.size(); ++i)
    ans[i - b.size() + 1] = _f[i];
  return ans;
}
inline std::vector<int> operator*=(std::vector<int> &a,
                                   const std::vector<int> &b) {
  return a = a * b;
}
template <typename _Tp>
inline std::vector<int> operator*=(std::vector<int> &a, const _Tp &b) {
  for (auto &&it : a) it = 1ULL * it * b % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator*(std::vector<int> a, const _Tp &b) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator*(const _Tp &b, std::vector<int> a) {
  return a *= b;
}
template <typename _Tp>
inline std::vector<int> operator/=(std::vector<int> &a, const _Tp &b) {
  unsigned long long inv = ksm(b);
  for (auto &&it : a) it = 1ULL * it * inv % mod;
  return a;
}
template <typename _Tp>
inline std::vector<int> operator/(std::vector<int> a, const _Tp &b) {
  return a /= b;
}
long long inv[N], ifac[N];
std::vector<int> e[N], w[N];
int siz[N], n, k, a[N], _[N];
std::vector<int> f[N << 1];
void sol1(int l, int r, int u) {
  if (l == r) return f[u] = {1, a[l]}, void();
  int mid = (l + r) >> 1;
  sol1(l, mid, u << 1), sol1(mid + 1, r, u << 1 | 1);
  f[u] = f[u << 1] * f[u << 1 | 1];
}
void sol2(int l, int r, int u, const std::vector<int> &g) {
  if (l == r) return _[l] = g[0], void();
  int mid = (l + r) >> 1;
  std::vector<int> tp = mulT(g, f[u << 1 | 1]);
  if (((int)tp.size()) > mid - l + 1) tp.resize(mid - l + 1);
  sol2(l, mid, u << 1, tp);
  tp = mulT(g, f[u << 1]);
  if (((int)tp.size()) > r - mid) tp.resize(r - mid);
  sol2(mid + 1, r, u << 1 | 1, tp);
}
void ___(int x, int fa) {
  std::sort(e[x].begin(), e[x].end());
  siz[x] = 1;
  for (auto v : e[x])
    if (v != fa) ___(v, x), siz[x] += siz[v];
  int pos = 0;
  for (auto v : e[x]) a[pos++] = v == fa ? n - siz[x] : siz[v];
  sol1(0, pos - 1, 1);
  std::vector<int> A(pos + 1);
  for (int i = 0; i <= pos; ++i) A[i] = k - i > 0 ? ifac[k - i] : 0;
  sol2(0, pos - 1, 1, A);
  w[x].resize(((int)e[x].size()));
  for (int i = 0; i < ((int)e[x].size()); ++i) w[x][i] = _[i];
}
bool vis[N];
int S, mn, rt;
int getsize(int x, int fa) {
  int siz = 1;
  for (auto v : e[x])
    if (v != fa && !vis[v]) siz += getsize(v, x);
  return siz;
}
void getrt(int x, int fa) {
  int tmp = 0;
  siz[x] = 1;
  for (auto v : e[x])
    if (v != fa && !vis[v]) getrt(v, x), chmax(tmp, siz[v]), siz[x] += siz[v];
  chmax(tmp, S - siz[x]);
  if (tmp < mn) mn = tmp, rt = x;
}
int QAQ, ans;
void dfs1(int x, int fa) {
  add(QAQ, w[x][std::lower_bound(e[x].begin(), e[x].end(), fa) - e[x].begin()]);
  for (auto v : e[x])
    if (v != fa && !vis[v]) dfs1(v, x);
}
void dfs(int x) {
  S = getsize(x, 0), mn = inf, getrt(x, 0), vis[x = rt] = true;
  int sum = 0;
  for (auto v : e[x])
    if (!vis[v])
      QAQ = 0, dfs1(v, x),
      add(ans, 1LL * QAQ *
                   w[x][std::lower_bound(e[x].begin(), e[x].end(), v) -
                        e[x].begin()] %
                   mod),
      add(ans, 1LL * sum * QAQ % mod), add(sum, QAQ);
  for (auto v : e[x])
    if (!vis[v]) dfs(v);
}
int main() {
  inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i < N; ++i)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod,
    ifac[i] = ifac[i - 1] * inv[i] % mod;
  setup();
  read(n, k);
  if (n == 1) return puts("0"), 0;
  for (int i = 1, x, y; i < n; ++i)
    read(x, y), e[x].push_back(y), e[y].push_back(x);
  ___(1, 0), dfs(1);
  for (int i = 1; i <= k; ++i) ans = 1LL * ans * i % mod * i % mod;
  printf("%d\n", ans);
  return 0;
}