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>
const int BUFFER_SIZE = 1 << 25 | 1;
struct InputOutputStream {
  char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE], *s, *oh;
  InputOutputStream() : s(ibuf), oh(obuf) {
    ibuf[fread(ibuf, 1, BUFFER_SIZE, stdin)] = '\0';
  }
  ~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }
  template <typename T>
  inline InputOutputStream &operator>>(T &x) {
    while (!isdigit(*s)) ++s;
    for (x = 0; isdigit(*s); ++s) x = x * 10 + (*s ^ '0');
    return *this;
  }
  template <typename T>
  inline InputOutputStream &operator<<(T x) {
    static char buf[23];
    register char *top = buf;
    if (x) {
      for (T t; x;) t = x / 10, *top++ = x - t * 10 + 48, x = t;
      while (top != buf) *oh++ = *--top;
    } else
      *oh++ = '0';
    *oh++ = ' ';
    return *this;
  }
} IO;
template <typename lhs, typename rhs>
inline lhs min(const lhs &x, const rhs &y) {
  return x < y ? x : y;
}
template <typename lhs, typename rhs>
inline lhs max(const lhs &x, const rhs &y) {
  return x > y ? x : y;
}
const int N_MAX = 131077;
int n, K;
std::vector<int> g[N_MAX];
const int mod = 998244353;
inline int power(int x, int y) {
  int o = 1;
  while (y) {
    if (y & 1) o = 1ll * o * x % mod;
    x = 1ll * x * x % mod, y >>= 1;
  }
  return o;
}
inline void operator+=(std::vector<int> &f, const std::vector<int> &g) {
  const int m = g.size();
  if ((int)f.size() < m) f.resize(m);
  for (int i = 0; i < m; ++i) f[i] = (f[i] + g[i]) % mod;
}
int unitRoot[N_MAX], rev[N_MAX];
inline int getLen(int n) { return 1 << (32 - __builtin_clz(n)); }
inline int prepare(int n) {
  const int len = getLen(n);
  for (int i = 1; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? len >> 1 : 0);
  return len;
}
inline void FFT(std::vector<int> &f, int len) {
  for (int i = 1; i < len; ++i)
    if (i < rev[i]) std::swap(f[i], f[rev[i]]);
  for (int i = 1; i < len; i <<= 1)
    for (int j = 0; j < len; j += i << 1)
      for (int k = 0; k < i; ++k) {
        int x = f[j | k], y = 1ll * f[i | j | k] * unitRoot[i | k] % mod;
        f[j | k] = (x + y) % mod, f[i | j | k] = (x - y) % mod;
      }
}
inline void operator*=(std::vector<int> &f, std::vector<int> g) {
  const int n = f.size(), m = g.size(), k = n + m - 1, len = prepare(k);
  f.resize(len), FFT(f, len), g.resize(len), FFT(g, len);
  for (int i = 0; i < len; ++i) f[i] = 1ll * f[i] * g[i] % mod;
  FFT(f, len), std::reverse(&f[1], &f[len]), f.resize(k);
  const int invLen = power(len, mod - 2);
  for (int i = 0; i < k; ++i) f[i] = 1ll * f[i] * invLen % mod;
}
inline std::vector<int> operator*(std::vector<int> f, std::vector<int> g) {
  f *= g;
  return f;
}
inline std::vector<int> makePoly(int a) {
  std::vector<int> temp(2);
  temp[0] = 1, temp[1] = a;
  return temp;
}
std::vector<int> *now;
std::vector<int> divideConquer(int l, int r) {
  if (l == r) return makePoly((*now)[l]);
  return divideConquer(l, ((l + r) >> 1)) *
         divideConquer(((l + r) >> 1) + 1, r);
}
inline void multiply(std::vector<int> &f, int a) {
  const int n = f.size();
  f.push_back(0);
  for (int i = n - 1; ~i; --i) f[i + 1] = (1ll * f[i] * a + f[i + 1]) % mod;
}
inline void divide(std::vector<int> &f, int a) {
  const int n = f.size(), inv = power(a, mod - 2);
  for (int i = n - 1; i; --i)
    f[i] = 1ll * f[i] * inv % mod, f[i - 1] = (f[i - 1] - f[i]) % mod;
  for (int i = 1; i < n; ++i) f[i - 1] = f[i];
  f.pop_back();
}
int fac[N_MAX], iFac[N_MAX];
inline int calc(std::vector<int> f) {
  const int n = min(K + 1, (int)f.size());
  int o = 0;
  for (int i = 0; i < n; ++i) o = (1ll * iFac[K - i] * f[i] + o) % mod;
  return 1ll * o * fac[K] % mod;
}
int ans, siz[N_MAX], dp[N_MAX], sum[N_MAX];
std::vector<int> pack[N_MAX];
int tub[N_MAX], vis[N_MAX], tim;
void dfs(int x, int f) {
  siz[x] = 1;
  std::vector<int> arr;
  for (int y : g[x])
    if (y != f) {
      dfs(y, x), siz[x] += siz[y], arr.push_back(siz[y]);
      ans = (1ll * sum[x] * sum[y] + ans) % mod;
      sum[x] = (sum[x] + sum[y]) % mod;
    }
  now = &arr;
  std::vector<int> temp =
      arr.size() ? divideConquer(0, arr.size() - 1) : makePoly(0);
  dp[x] = calc(temp), sum[x] = (sum[x] + dp[x]) % mod;
  multiply(temp, n - siz[x]), ++tim;
  for (int y : g[x])
    if (y != f) {
      if (vis[siz[y]] == tim)
        ans = (1ll * sum[y] * tub[siz[y]] + ans) % mod;
      else {
        vis[siz[y]] = tim;
        divide(temp, siz[y]);
        ans = (1ll * sum[y] * (tub[siz[y]] = calc(temp)) + ans) % mod;
        multiply(temp, siz[y]);
      }
    }
}
int main() {
  IO >> n >> K;
  if (K == 1) {
    printf("%lld\n", 499122177ll * n * (n - 1) % mod);
    return 0;
  }
  for (int i = 1; i < n; ++i) {
    int x, y;
    IO >> x >> y;
    g[x].push_back(y), g[y].push_back(x);
  }
  fac[0] = 1;
  for (int i = 1; i <= K; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
  iFac[K] = power(fac[K], mod - 2);
  for (int i = K; i; --i) iFac[i - 1] = 1ll * iFac[i] * i % mod;
  const int len = getLen(n);
  for (int i = 1; i < len; i <<= 1) {
    const int temp = power(3, (mod - 1) / (i << 1));
    unitRoot[i] = 1;
    for (int j = 1; j < i; ++j)
      unitRoot[i | j] = 1ll * unitRoot[(i | j) - 1] * temp % mod;
  }
  dfs(1, 0);
  printf("%d\n", (ans + mod) % mod);
  return 0;
}