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;
inline void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = v * 10 + c - '0';
  while (isdigit(c = getchar())) v = v * 10 + c - '0';
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while ((c = getchar()) == ' ')
    ;
  x = c;
}
inline void writes(string s) { puts(s.c_str()); }
inline void writeln() { writes(""); }
inline void writei(int x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
inline void writell(long long x) {
  if (x < 0) {
    putchar('-');
    x = abs(x);
  }
  if (!x) putchar('0');
  char a[25];
  int top = 0;
  while (x) {
    a[++top] = (x % 10) + '0';
    x /= 10;
  }
  while (top) {
    putchar(a[top]);
    top--;
  }
}
long long n, m, i, j, sz[262145], x, y, f[262145], dp[262145],
    mod = 998244353, fac[262145], inv[262145], first[262145], lg[262145],
    pw[262145], w[262145], iw[262145], ans;
long long rev[262145], a[262145], b[262145];
vector<long long> seq, e[262145], tmp;
bool cmp(long long x, long long y) { return sz[x] < sz[y]; }
long long calc(vector<long long> &v) {
  long long s = 0, i;
  for (i = 0; i < min(m + 1, (long long)v.size()); i++) {
    (s += 1ll * v[i] * fac[m] % mod * first[m - i]) %= mod;
  }
  return s;
}
long long mpw(long long x, long long y) {
  long long z = 1;
  while (y) {
    if (y & 1) z = 1ll * z * x % mod;
    y >>= 1;
    x = 1ll * x * x % mod;
  }
  return z;
}
void init() {
  long long i;
  for ((i) = (2); (i) <= (262143); (i)++) lg[i] = lg[i >> 1] + 1;
  pw[0] = 1;
  for (((i)) = (1); ((i)) <= ((lg[262144])); ((i))++) pw[i] = pw[i - 1] * 2;
  w[0] = 1;
  w[1] = mpw(3, (mod - 1) / 262144);
  for ((i) = (2); (i) <= (262144); (i)++) w[i] = 1ll * w[i - 1] * w[1] % mod;
  iw[262144] = mpw(w[262144], mod - 2);
  for ((i) = (262143); (i) >= (0); (i)--) iw[i] = 1ll * iw[i + 1] * w[1] % mod;
}
long long getrev(long long x) {
  long long i, s = 1;
  while (s < x) s *= 2;
  rev[0] = 0;
  for (((i)) = (1); ((i)) <= ((s - 1)); ((i))++)
    rev[i] = ((rev[i >> 1] >> 1) | ((i & 1) << (lg[s] - 1)));
  return s;
}
void ntt(long long *a, long long n, long long *w) {
  long long i, j, k;
  for ((i) = (0); (i) <= (n - 1); (i)++)
    if (rev[i] < i) swap(a[i], a[rev[i]]);
  for (i = 1; i < n; i <<= 1) {
    long long ys = 262144 / i / 2;
    for (j = 0; j < n; j += i + i) {
      long long *t = w;
      for ((k) = (0); (k) <= (i - 1); (k)++) {
        long long x = a[j + k], y = 1ll * a[j + k + i] * (*t) % mod;
        a[j + k] = x + y;
        if (a[j + k] >= mod) a[j + k] -= mod;
        a[j + k + i] = x - y;
        if (a[j + k + i] < 0) a[j + k + i] += mod;
        t += ys;
      }
    }
  }
}
vector<long long> operator*(const vector<long long> &aa,
                            const vector<long long> &bb) {
  vector<long long> ans;
  long long br = 1ll * aa.size() * bb.size(),
            ft =
                1ll * (aa.size() + bb.size()) * lg[aa.size() + bb.size()] * 10 +
                100;
  if (br < ft) {
    while (ans.size() + 1 < aa.size() + bb.size()) ans.push_back(0);
    long long i, j;
    for (i = 0; i < aa.size(); i++)
      for (j = 0; j < bb.size(); j++) {
        ans[i + j] += 1ll * aa[i] * bb[j] % mod;
        ans[i + j] %= mod;
      }
  } else {
    long long len = getrev(aa.size() + bb.size()), i;
    for (i = 0; i < len; i++) a[i] = b[i] = 0;
    for (i = 0; i < aa.size(); i++) a[i] = aa[i];
    for (i = 0; i < bb.size(); i++) b[i] = bb[i];
    ntt(a, len, w);
    ntt(b, len, w);
    for (i = 0; i < len; i++) a[i] = 1ll * a[i] * b[i] % mod;
    ntt(a, len, iw);
    long long inv = mpw(len, mod - 2);
    for (i = 0; i < len; i++) ans.push_back(1ll * a[i] * inv % mod);
  }
  while (!ans.empty() && !ans.back()) ans.pop_back();
  return ans;
}
void solve(vector<long long> &ans, const vector<long long> &all, long long l,
           long long r) {
  long long mid = (l + r) / 2;
  if (l > r) {
    ans.push_back(1);
    return;
  }
  if (l == r) {
    ans.push_back(1);
    ans.push_back(sz[all[l]]);
    return;
  }
  vector<long long> sl, sr;
  solve(sl, all, l, mid);
  solve(sr, all, mid + 1, r);
  ans = sl * sr;
}
void dfs1(long long x, long long fa) {
  sz[x] = 1;
  for (__typeof((e[x]).begin()) it = (e[x]).begin(); it != (e[x]).end(); it++)
    if (*it != fa) {
      dfs1(*it, x);
      sz[x] += sz[*it];
      (dp[x] += dp[*it]) %= mod;
    }
  vector<long long> all;
  for (__typeof((e[x]).begin()) it = (e[x]).begin(); it != (e[x]).end(); it++)
    if (*it != fa) all.push_back(*it);
  seq.clear();
  solve(seq, all, 0, ((long long)all.size()) - 1);
  f[x] = calc(seq);
  (dp[x] += f[x]) %= mod;
  seq.push_back(0);
  for ((i) = (seq.size() - 1); (i) >= (1); (i)--) {
    (seq[i] += 1ll * seq[i - 1] * (n - sz[x]) % mod) %= mod;
  }
  long long i, lst = 0;
  for (i = 0; i < all.size(); i++) {
    if (i && sz[all[i - 1]] == sz[all[i]]) {
      ans += 1ll * dp[all[i]] * lst % mod;
      ans %= mod;
      continue;
    }
    vector<long long> tmp = seq;
    for (j = 1; j < tmp.size(); j++) {
      tmp[j] -= 1ll * tmp[j - 1] * sz[all[i]] % mod;
      tmp[j] += mod;
      tmp[j] %= mod;
    }
    lst = calc(tmp);
    ans += 1ll * dp[all[i]] * lst % mod;
    ans %= mod;
  }
}
void dfs2(long long x, long long fa) {
  long long s = 0;
  for (__typeof((e[x]).begin()) it = (e[x]).begin(); it != (e[x]).end(); it++)
    if (*it != fa) {
      dfs2(*it, x);
      ans += 1ll * s * dp[*it] % mod;
      ans %= mod;
      s += dp[*it];
      s %= mod;
    }
}
int main() {
  read(n);
  read(m);
  if (m == 1) {
    cout << 1ll * n * (n - 1) / 2 % mod << endl;
    return 0;
  }
  fac[0] = fac[1] = first[0] = first[1] = inv[0] = inv[1] = 1;
  for ((i) = (2); (i) <= (max(m, n)); (i)++) {
    fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    first[i] = 1ll * first[i - 1] * inv[i] % mod;
  }
  for (((i)) = (1); ((i)) <= ((n - 1)); ((i))++) {
    read(x);
    read(y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  init();
  dfs1(1, 0);
  dfs2(1, 0);
  cout << ans << endl;
  return 0;
}