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;
int power(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = 1ll * res * a % 998244353;
    a = 1ll * a * a % 998244353;
    b = b >> 1;
  }
  return res;
}
namespace NTT {
int rev[400010];
int ww[400010 << 1], *g = ww + 400010;
int a[400010], b[400010];
int init(int n) {
  int len, l;
  for (len = 1, l = 0; len <= n; len = len << 1, ++l)
    ;
  for (int i = 0; i < len; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
  g[0] = g[-len] = 1;
  g[1] = g[1 - len] = power(3, (998244353 - 1) / len);
  for (int i = 2; i < len; ++i)
    g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % 998244353;
  return len;
}
void NTT(int f[], int l, int ty) {
  for (int i = 0; i < l; ++i)
    if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int i = 2; i <= l; i = i << 1) {
    int wn = g[ty * l / i];
    for (int j = 0; j < l; j += i) {
      int w = 1;
      for (int k = j; k < j + i / 2; ++k) {
        int u = f[k], t = 1ll * w * f[k + i / 2] % 998244353;
        f[k] = (u + t) % 998244353;
        f[k + i / 2] = (u - t + 998244353) % 998244353;
        w = 1ll * w * wn % 998244353;
      }
    }
  }
  if (ty == -1) {
    int inv = power(l, 998244353 - 2);
    for (int i = 0; i < l; ++i) f[i] = 1ll * f[i] * inv % 998244353;
  }
  return;
}
}  // namespace NTT
int fac[400010], ifac[400010];
int n, m;
struct edge {
  int to, nxt;
} e[400010 << 1];
int edgenum = 0;
int lin[400010] = {0};
void add(int a, int b) {
  ++edgenum;
  e[edgenum].to = b;
  e[edgenum].nxt = lin[a];
  lin[a] = edgenum;
  ++edgenum;
  e[edgenum].to = a;
  e[edgenum].nxt = lin[b];
  lin[b] = edgenum;
  return;
}
int siz[400010], degs[400010];
int sizs[400010], cnt = 0;
int fg[400010];
int fun[400010];
void solve(int k, int l, int r) {
  using namespace NTT;
  if (r <= l) return;
  if (r - l == 1) {
    fun[l] = sizs[l];
    return;
  }
  int mid = ((l + r) >> 1);
  solve(k, l, mid);
  solve(k, mid, r);
  a[0] = b[0] = 1;
  for (int i = 1, j = l; i <= mid - l; ++i, ++j) a[i] = fun[j];
  for (int i = 1, j = mid; i <= r - mid; ++i, ++j) b[i] = fun[j];
  int len = init(r - l);
  NTT::NTT(a, len, 1);
  NTT::NTT(b, len, 1);
  for (int i = 0; i < len; ++i) a[i] = 1ll * a[i] * b[i] % 998244353;
  NTT::NTT(a, len, -1);
  for (int i = 1, j = l; i <= r - l; ++i, ++j) fun[j] = a[i];
  for (int i = 0; i < len; ++i) a[i] = b[i] = 0;
  return;
}
int f[400010];
int valg[400010];
int nfg[400010];
void divide(int k, int siz) {
  for (int i = 0; i <= degs[k] + 1; ++i) nfg[i] = fg[i];
  int invsiz = power(siz, 998244353 - 2);
  for (int i = degs[k] + 1; i >= 1; --i) {
    int v = 1ll * nfg[i] * invsiz % 998244353;
    nfg[i] = v;
    nfg[i - 1] = (nfg[i - 1] - v + 998244353) % 998244353;
  }
  for (int i = 0; i <= degs[k]; ++i) nfg[i] = nfg[i + 1];
  nfg[degs[k] + 1] = 0;
  return;
}
int g[400010];
void dfs(int k, int fa) {
  siz[k] = 1;
  for (int i = lin[k]; i != 0; i = e[i].nxt) {
    if (siz[e[i].to]) continue;
    dfs(e[i].to, k);
    ++degs[k];
    siz[k] += siz[e[i].to];
  }
  cnt = 0;
  for (int i = lin[k]; i != 0; i = e[i].nxt) {
    if (e[i].to == fa) continue;
    sizs[cnt++] = siz[e[i].to];
  }
  solve(k, 0, degs[k]);
  for (int i = degs[k]; i >= 1; --i) fun[i] = fun[i - 1];
  fun[0] = 1;
  for (int i = 0; i <= min(degs[k], m); ++i)
    f[k] =
        (f[k] + 1ll * fac[m] * ifac[m - i] % 998244353 * fun[i] % 998244353) %
        998244353;
  sort(sizs, sizs + cnt);
  cnt = unique(sizs, sizs + cnt) - sizs;
  for (int i = 0; i <= degs[k]; ++i) fg[i] = fun[i];
  for (int i = 0; i <= degs[k]; ++i)
    fg[i + 1] =
        (fg[i + 1] + 1ll * fun[i] * (n - siz[k]) % 998244353) % 998244353;
  for (int i = 0; i < cnt; ++i) {
    int ss = sizs[i];
    divide(k, ss);
    for (int i = 0; i <= min(degs[k], m); ++i)
      g[ss] = (g[ss] +
               1ll * nfg[i] * fac[m] % 998244353 * ifac[m - i] % 998244353) %
              998244353;
    for (int i = 0; i <= degs[k] + 1; ++i) nfg[i] = 0;
  }
  for (int i = 0; i <= degs[k] + 1; ++i) fg[i] = fun[i] = 0;
  for (int i = lin[k]; i != 0; i = e[i].nxt) valg[e[i].to] = g[siz[e[i].to]];
  for (int i = 0; i < cnt; ++i) g[sizs[i]] = 0;
  return;
}
int sumf[400010];
int ans = 0;
void dfs2(int k, int fa) {
  sumf[k] = f[k];
  for (int i = lin[k]; i != 0; i = e[i].nxt) {
    if (e[i].to == fa) continue;
    dfs2(e[i].to, k);
    sumf[k] = (sumf[k] + sumf[e[i].to]) % 998244353;
    ans = (ans + 1ll * sumf[e[i].to] * valg[e[i].to] % 998244353) % 998244353;
    ans =
        (ans - 1ll * sumf[e[i].to] * f[k] % 998244353 + 998244353) % 998244353;
  }
  return;
}
int main() {
  scanf("%d%d", &n, &m);
  if (m == 1) {
    cout << 1ll * n * (n - 1) / 2 % 998244353 << endl;
    return 0;
  }
  fac[0] = 1;
  for (int i = 1; i <= m; ++i) fac[i] = 1ll * fac[i - 1] * i % 998244353;
  ifac[m] = power(fac[m], 998244353 - 2);
  for (int i = m - 1; i >= 0; --i)
    ifac[i] = 1ll * ifac[i + 1] * (i + 1) % 998244353;
  int a, b;
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &a, &b);
    add(a, b);
  }
  dfs(1, 0);
  dfs2(1, 0);
  int sum = 0;
  for (int i = 1; i <= n; ++i) sum = (sum + f[i]) % 998244353;
  sum = 1ll * sum * sum % 998244353;
  for (int i = 1; i <= n; ++i)
    sum = (sum - 1ll * f[i] * f[i] % 998244353 + 998244353) % 998244353;
  sum = 1ll * sum * power(2, 998244353 - 2) % 998244353;
  ans = (ans + sum) % 998244353;
  cout << ans << endl;
  return 0;
}